generate sequence with all permutations

Question

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 possible permutations: 123, 231, 312, 121 (invalid), 213, 132, 321.

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

Answer 1

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

Answer 2

This greedy algorithm appears to produce minimal sequences.

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

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