Questions tagged [permutations]

A permutation is a particular ordering of some list of objects. Problems tagged with permutation usually involve finding or generating permutations, including anagrams of text.

Filter by
Sorted by
Tagged with
23
votes
12answers
2k views

Number of cycles of a permutation

Consider a permutation of the integers 1, ..., n, such as this one for n = 6: ...
9
votes
6answers
357 views

Print the “even” permutations of symmetric group Sn in cyclic notation

THE TASK DEFINITIONS Consider the points {1,2,3,4,5} and all their permutations. We can find the total number of possible permutations of these 5 points by a simple trick: Imaging filling 5 slots ...
2
votes
2answers
225 views

Marching Through A City

There is a parade marching through a city! There are 3 main groups of marchers: the (B)and, Poster (C)arriers, and (F)lag Holders. Also, every (P)oliceman in the whole city is on duty. Flag holders (...
14
votes
21answers
3k views

Golf bit weaving

Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving. The esoteric programming language evil has an interesting operation on byte values which it ...
28
votes
27answers
2k views

Bit-Reversal Permutations

Your goal is to create a function or a program to reverse the bits in a range of integers given an integer n. In other words, you want to find the bit-reversal permutation of a range of 2n items, zero-...
31
votes
20answers
2k views

Faro shuffle an array

A Faro shuffle is a technique frequently used by magicians to "shuffle" a deck. To perform a Faro shuffle you first cut the deck into 2 equal halves then you interleave the two halves. For example <...
11
votes
7answers
512 views

Find a function with cycles of every length

A function is said to have a cycle of length n if there exists an x in its domain such that fn(x) = x and fm(x) ≠ x for 0 < m < n, where the superscript n denotes n-fold application of f. Note ...
12
votes
2answers
267 views

Rotation-safe Latin squares

A Latin square is a square that has no repeated symbols in either the X or Y columns. For example: ABCD DABC CDAB BCDA is one such square. Notice how every ...
12
votes
10answers
819 views

Permutations with Indistinguishable Items

Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each ...
13
votes
6answers
787 views

Magic number of a given length

Your program must take an input (n for the purpose of description) and output all permutations of a number that is n digits long ...
21
votes
12answers
2k views

All possible ways to interleave two strings

I recently saw this question on stackoverflow. It's a great question, but there's one fatal problem with the question. They are asking for the best way to do it. E.g, easiest to read, most idiomatic, ...
16
votes
24answers
2k views

Random array without repetition

I was answering one challenge here and this task was part of the challenge. I've got a 73 bytes solution in javascript. But I think it is too much for a simple thing. Challenge Given as input two ...
14
votes
8answers
1k views

Parity of a Permutation

Background The parity of a permutation, as defined by wikipedia, is as follows: The sign or signature of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd. ...
21
votes
3answers
395 views

Permutation Square Root

In math, a permutation σ of order n is a bijective function from the integers 1...n to itself. This list: 2 1 4 3 represents the permutation σ such that σ(1) = 2,...
35
votes
32answers
2k views

Manage Trash So

It's become somewhat of a tradition in PPCG that some users temporarily change their names by an anagram (a new name formed by reordering the letters of the old). Sometimes it gets difficult to find ...
19
votes
11answers
618 views

Maximise the squared difference

Consider a permutation of the integer values from 1 to N. E.g. this example for N = 4: <...
23
votes
27answers
2k views

Rearranging the sequence

Introduction Let's observe the following sequence (non-negative integers): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... For example, let's take the ...
17
votes
8answers
757 views

Spiral Permutation Sequence

We can roll up the natural numbers in a rectangular spiral: ...
10
votes
2answers
246 views

The absent-minded linguist

Background Your friend, a linguist, has recorded and analyzed some simple conversation snippets in various languages. Being quite absent-minded, they have forgotten which language each snippet was in....
14
votes
6answers
589 views

Letters, Get Moving! Pt. 2

The first Letters, Get Moving! was very popular, but had limited participation. This one will be easier to solve, but hopefully involve some tricks in golfing. You are given a string of only ...
15
votes
2answers
307 views

Can the Array be Unshuffled?

Background Very skilled card handlers are capable of a technique whereby they cut a deck perfectly in half, then perfectly interleave the cards. If they start with a sorted deck and perform this ...
17
votes
2answers
966 views

Random Golf of the Day #6: Roll a d20

About the Series First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
16
votes
6answers
389 views

Find maximal matching in divisibility relation

You are given a set of positive integers. You must arrange them into pairs such that: Each pair contains 2 numbers, one of which is a multiple of another. For example, 8 is a multiple of 4, and 9 is ...
10
votes
4answers
297 views

Rearrangement Inequality

Background The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same ...
12
votes
8answers
500 views

Typesetting multidimensional labels

In a steam-punk multidimensional world, our boss wants to affix printed index labels to each drawer in our conglomerate's multidimensional file cabinet. The boss wants to typeset the entire label ...
17
votes
14answers
848 views

Fun With Permutations

Who doesn't absolutely love permutations, right? I know, they are amazing––so much fun! Well, why not take this fun and make it funner? Here's the challenge: Given an input in the exact form: ...
24
votes
20answers
2k views

Imitate an ordering

Given two lists of numbers, a source and a pattern, reorder the source to match the relative ordering of the pattern. Any two entries of the reordered source should compare the same way as the entries ...
14
votes
17answers
954 views

Code Golf: Forwards sdrawkcaB sdrawkcaB Forwards Forwards sdrawkcaB

Task The user inputs a sentence - words only. Any input other than letters or spaces, including integers and punctuation, should throw an exception: "Sentence must only use letters". The output has a ...
20
votes
2answers
1k views

The Combinatorics of Transistor

The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and ...
11
votes
3answers
427 views

Possible Tetris sequences

Write code to figure out whether a run of Tetris pieces could be generated by the official Tetris algorithm. Fewest bytes wins. Official Tetris games generate the sequence of falling pieces in a ...
34
votes
6answers
2k views

Can you reach this number by doubling and rearranging?

Inspired by this question on Math.SE. Starting with 1 you can repeatedly perform one of the following two operations: Double the number. or Rearrange its digits ...
10
votes
5answers
622 views

Cycle lengths for Perfect shuffles of decks of any size

Challenge In the shortest amount of code: Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even). Output a table of all cycle ...
14
votes
8answers
982 views

Alphabetic Fannkuch

Fannkuch is a classic benchmark program. The name comes from the German "Pfannkuchen"- pancakes- for the algorithm's resemblance to flipping stacks of pancakes. A Fannkuch sequence of numbers is ...
21
votes
13answers
1k views

Every Possible Cycle Length

A function (or program) which takes inputs and provides outputs can be said to have a cycle if calling the function on its own output repeatedly eventually reaches the original number. For instance, ...
13
votes
5answers
406 views

Permutations of the Fifteen Puzzle

The Challenge Consider the following diagram of the Fifteen Puzzle in its solved state: ...
7
votes
3answers
286 views

Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime

Let n > 0. Let X = [1..n] and Y = [n+1 .. 2n]. Define ...
3
votes
1answer
350 views

Plus one sheep minus one sheep [closed]

Once upon a time long long ago... when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided ...
8
votes
7answers
348 views

Detecting anagrams within a Parent String

Given two strings, a parent string and a query string respectively, your task is to determine how many times the query string, or an anagram of the query string; appears in the parent string, in a ...
15
votes
4answers
447 views

Order 40 sticks

We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from ...
12
votes
3answers
628 views

Count the number of Hankelable matrices

Background A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1...
16
votes
3answers
849 views

Reconstruct a Permutation

Introduction Suppose that you are handed a random permutation of n objects. The permutation is sealed in a box, so you have no idea which of the ...
11
votes
1answer
705 views

Constructing an Orthogonal-Diagonal Greco-Latin Square

Consider a grid of NxN unique elements. Each element has a letter (from A to the Nth letter,...
45
votes
19answers
5k views

Shotgun Numbers

The Shotgun numbers are a sequence with a rather simple definition but some interesting structure. Start with the natural numbers: ...
11
votes
5answers
507 views

Total number of topological sorts

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation. Your task is ...
20
votes
3answers
1k views

Anagramming Stack Exchange question titles into programs

Stack Exchange currently has 134 question and answer sites. This includes all beta sites (such as PPCG) but not Area 51 proposals nor any meta sites, except for the "mother meta". To answer this ...
35
votes
35answers
6k views

Random Golf of the Day #1: Shuffle an Array

About the Series I will be running a little series of code-golf challenges revolving around the theme of randomness. This will basically be a 9-Hole Golf Course, but spread out over several questions....
16
votes
7answers
2k views

Typing with scrambled keys

Your friend isn't too good with computers so as a practical joke someone scrambled the letters (a-z) on his keyboard. When he sit down and tried to type his name looking at the keyboard he realized ...
-2
votes
2answers
923 views

Find Anagrams in the Dictionary [closed]

This a code challenge. The winner will be the person to provide the most efficient implementation of the solution in terms of algorithmic complexity. Using the dictionary found in '/usr/share/dict' (...
9
votes
4answers
560 views

Curator's Dilemma

Introduction You are a friend of a curator for an art museum, who has had the recent delight of getting modern art from four artists (some of which may give the curator zero pieces of art, young ...
21
votes
5answers
7k views

Sort a List With Swaps and Pops

Consider a randomized list of the integers 1 to N. You want to sort it using only the following actions: Swap the first and last list elements. (S) Pop off the first element and append it to the end ...