generate sequence with all permutations

• 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.

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!²).

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.