<p>This greedy algorithm produces fairly short minimal sequences.</p>

<blockquote>
  <p><strong>UPDATE: Note that <a href="https://arxiv.org/abs/1408.5108" rel="nofollow noreferrer">for <em>n</em> &ge; 6, this algorithm does not produce the shortest possible string!</a></strong></p>
</blockquote>

<ul>
<li>Make a collection of all permutations.</li>
<li>Remove the first permutation from the collection.</li>
<li>Let <em>a</em> = the first permutation.</li>
<li>Find the sequence in the collection that has the greatest overlap with the end of <em>a</em>. 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 <em>a</em>. Repeat this step until the collection is empty.</li>
</ul>

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

<p>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.</p>

<p>The algorithm is O(<em>n</em>!<sup>2</sup>).</p>

<p>An implementation in Python:</p>

<pre><code>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
</code></pre>

<p>The length of the strings generated by this function are 1, 3, 9, 33, 153, 873, 5913, ... which appears to be <a href="https://oeis.org/A007489" rel="nofollow noreferrer">this integer sequence</a>.</p>

<p>I have a hunch you can do better than O(<em>n</em>!<sup>2</sup>).</p>
generate sequence with all permutations
<p>How can I generate the shortest sequence with contains all possible permutations?</p>

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

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

<p>Each number (within a given permutation) may only occur once.</p>