generate sequence with all permutations_问答_开发者

How can I generate the shortest sequence with contains 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 possib开发者_JAVA百科le permutations: 123, 231, 312, 121 (invalid), 213, 132, 321.

Each number (within a given permutation) may only occur once.

This greedy algorithm produces fairly short minimal sequences.

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

Make a collection of all permutations.
Remove the first permutation from the collection.
Let a = the first permutation.
Find the sequence in the collection that has the greatest overlap with the end of a. If there is a tie, choose the sequence is first in lexicographic order. Remove the chosen sequence from the collection and add the non-overlapping part to the end of a. Repeat this step until the collection is empty.

The curious tie-breaking step is necessary for correctness; breaking the tie at random instead seems to result in longer strings.

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

The algorithm is O(n!²).

An implementation in Python:

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 strings generated by this function are 1, 3, 9, 33, 153, 873, 5913, ... which appears to be this integer sequence.

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

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

Here is a fast algorithm that produces a short string containing all permutations. I am pretty sure it produces the shortest possible answer, but I don't have a complete proof in hand.

Explanation. Below is a tree of All Permutations. The picture 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 the permutations of length k. Furthermore, the permutations are in a particular order with a lot of overlap between each permutation and its neighbors above and below.

To be precise, each node's first child is found by simply adding the next symbol to the end. For example, the first child of 213 would be 2134. The rest of the children are found by rotating to the first child to left one symbol at a time. Rotating 2134 would produce 1342, 3421, 4213.

Taking all the nodes at a given level and stringing them together, overlapping as much as possible, produces the strings 1, 121, 123121321, etc.

The length of the nth string in that sequence is the sum for x=1 to n of x!. (You can prove this by observing how much non-overlap there is between neighboring permutations. Siblings overlap in all but 1 symbol; first-cousins overlap in all but 2 symbols; and so on.)

Sketch of proof. I haven't completely proved that this is the best solution, but here's a sketch of how the proof would proceed. First show that any string containing n distinct permutations has length ≥ 2n - 1. Then show that adding any string containing n+1 distinct permutations has length 2n + 1. That is, adding one more permutation will cost you two digits. Proceed by calculating the minimum length of strings containing _nP_r and _nP_r + 1 distinct permutations, up to n!. In short, this sequence is optimal because you can't make it worse somewhere in the hope of making it better someplace else. It's already locally optimal everywhere. All the moves are forced.

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

Fortunately we do not actually have to build the 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's left

def stringContainingAllPermutationsOf(s):
    return build(s[:1], s)

Performance. The above code is already much faster than my other solution, and it does a lot of cutting and pasting of large strings that you can optimize away. The algorithm can be made to run in time and memory proportional to the size of the output.

For n 3 length chain is 8 12312132 Seems to me we are working with cycled system - it's ring, saying in other words. But we are are working with ring as if it is chain. Chain is realy 123121321 = 9 But the ring is 12312132 = 8 We take last 1 for 321 from the beginning of the sequence 12312132[1].

These are called (minimal length) superpermutations (cf. Wikipedia). Interest on this has re-sparked when an anonymous user has posted a new lower bound on 4chan. (See Wikipedia and many other web pages for history.)

AFAIK, as of today we just know:

Their length is A180632(n) ≤ A007489(n) = Sum_{k=1..n} k! but this bound is only sharp for n ≤ 5, i.e., we have equality for n ≤ 5 but strictly less for n > 5.
There's a very simple recursive algorithm, given below, producing a superpermutation of length A007489(n), which is always palindromic (but as said above this is not the minimal length for n > 5).
For n ≥ 7 we have the better upper bound n! + (n−1)! + (n−2)! + (n−3)! + n − 3.
For n ≤ 5 all minimal SP's are known; and for all n > 5 we don't know which is the minimal SP.
For n = 1, 2, 3, 4 the minimal SP's are unique (up to changing the symbols), given by (1, 121, 123121321, 123412314231243121342132413214321) of length A007489(1..4) = (1, 3, 9, 33).
For n = 5 there are 8 inequivalent ones of minimal length 153 = A007489(5); the palindromic one produced by the algorithm below is the 3rd in lexicographic order.
For n = 6 Houston produced thousands of the smallest known length 872 = A007489(6) - 1, but AFAIK we still don't know whether this is minimal.
For n = 7 Egan produced one of length 5906 (one less than the better upper bound given above) but again we don't know whether that's minimal.

I've written a very short PARI/GP program (you can paste to run it on the PARI/GP web site) which implements the standard algorithm producing a palindromic superpermutation of length A007489(n):

extend(S,n=vecmax(s))={ my(t); concat([
  if(#Set(s)<n, [], /* discard if not a permutation */
    s=concat([s, n+1, s]); /* Now merge with preceding segment: */ 
    forstep(i=min(#s, #t)-1, 0, -1,
      if(s[1..1+i]==t[#t-i..#t], s=s[2+i..-1]; break));
    t=s /* store as previous for next */
  )/*endif*/
  | s <- [ S[i+1..i+n] | i <- [0..#S-n] ]])
}
SSP=vector(6, n, s=if(n>1, extend(s), [1])); // gives the first 6, the 6th being non-minimal

I think that easily translates to any other language. (For non-PARI speaking persons: "| x <-" means "for x in".)