Generate a sequence with all permutations

Question

How can I generate the shortest sequence with all possible permutations?

Example: For length 2, the answer is 121, because this list contains 12 and 21, which are all possible permutations.

For length 3, the answer is 123121321, because this list contains all the possible permutations: 123, 231, 312, 121 (invalid), 213, 132, 321.

Each number (within a given permutation) can appear only once.

Answer 1

This greedy algorithm gives fairly short minimal sequences.

UPDATE: Note that for n ≥ 6 this algorithm does not produce the shortest string!

• Create a collection of all permutations.
• Remove the first permutation from the collection.
• Let a = first permutation.
• Find the sequence in the collection that matches the end a most. If there is a tie, select the sequence first in lexicographical order. Remove the selected sequence from the collection and add the non-overlapping portion to the end. Repeat this step until the collection is empty.

For correctness, a curious tightening step is necessary; breaking the tie at random seems to result in longer lines.

I checked (by writing a much longer and slower program) that the answer this algorithm gives for length 4, 123412314231243121342132413214321, is really the shortest answer. However, for length 6, it gives an answer of length 873, which is longer than the shortest known solution.

Algorithm O (n! ² ).

Python implementation:

import itertools def costToAdd(a, b): for i in range(1, len(b)): if a.endswith(b[:-i]): return i return len(b) def stringContainingAllPermutationsOf(s): perms = set(''.join(tpl) for tpl in itertools.permutations(s)) perms.remove(s) a = s while perms: cost, next = min((costToAdd(a, x), x) for x in perms) perms.remove(next) a += next[-cost:] return a 

The length of the lines generated by this function is 1, 3, 9, 33, 153, 873, 5913, ... which is represented by this integer sequence .

I have a suspicion that you can do better than O (n! ² ).

Answer 2

• Create all permutations.
• Let each permutation be a node in the graph.
• Now, for any two states, add an edge with a value of 1 if they separate n-1 digits (for the source from the end, and for the target from the end), two if they separate the digits n-2 and so on.
• Now you need to find the shortest path containing n vertices.

Answer 3

Here is a quick algorithm that creates a short string containing all permutations. I am sure that he gives the shortest answer, but I do not have complete evidence in my hand.

Explanation. Below is a tree of all permutations. The image is incomplete; imagine that the tree goes on forever to the right.

 1 --+-- 12 --+-- 123 ... | | | +-- 231 ... | | | +-- 312 ... | +-- 21 --+-- 213 ... | +-- 132 ... | +-- 321 ... 

The nodes at level k of this tree are all permutations of length k. In addition, permutations in a certain order with a large amount of overlap between each permutation and its neighbors above and below.

To be precise, each node of the first child is found by simply adding the next character to the end. For example, the first child of 213 will be 2134. The rest of the children can be found by turning to the first child to leave one character at a time. A rotation of 2134 will produce 1342, 3421, 4213.

Taking all the nodes at a given level and linking them together, overlapping as much as possible, creates lines 1, 121, 123121321, etc.

The length of the string n in this sequence is the sum for x = 1 to n of x! . (You can prove this by observing how much does not overlap between adjacent permutations. Siblings overlap in all characters except one, the first cousins ​​overlap in all but two characters, etc.)

Sketch of evidence. I have not fully proved that this is the best solution, but here is a sketch of how the proof will continue. First show that any string containing n different permutations is & ge; 2 n - 1. Then show that adding any line containing n + 1 different permutations is 2 n + 1. That is, adding another permutation will cost you two digits. Continue to calculate the minimum length of lines containing _n P _r and _n P _r + 1 different permutations, up to n !. In short, this sequence is optimal because you cannot make it worse somewhere in the hope of making it better somewhere else. It is already locally optimal everywhere. All movements are forced.

Algorithm. Given all this background, the algorithm is very simple. Walk this tree to the desired depth and connect all the nodes at this depth.

Fortunately, we actually do not need to build a tree in memory.

 def build(node, s): """String together all descendants of the given node at the target depth.""" d = len(node) # depth of this node. depth of "213" is 3. n = len(s) # target depth if d == n - 1: return node + s[n - 1] + node # children of 213 join to make "2134213" else: c0 = node + s[d] # first child node children = [c0[i:] + c0[:i] for i in range(d + 1)] # all child nodes strings = [build(c, s) for c in children] # recurse to the desired depth for j in range(1, d + 1): strings[j] = strings[j][d:] # cut off overlap with previous sibling return ''.join(strings) # join what left def stringContainingAllPermutationsOf(s): return build(s[:1], s) 

Performance. The above code is already much faster than my other solution, and it cuts and inserts large lines a lot, which you can optimize. The algorithm can be executed in time and in memory proportional to the size of the output.

Answer 4

For n 3, the chain length is 8 12312132 It seems we are working with a cyclic system - this is a ring, in other words. But we work with the ring as if it were a chain. The chain is really 123121321 = 9 But the ring 12312132 = 8 We take the last 1 for 321 from the beginning of the sequence 1 2312132 [1].