What is the shortest sequence that contains every permutation of $1..n$? [duplicate]

Possible Duplicate:
What is the shortest string that contains all permutations of an alphabet?

How can one create a list of numbers so that by taking $n$ consecutive elements from that list, it is possible get every permutation of numbers from 1 to $n$?

I'll explain myself:

The shortest list that contains every permutation of the numbers from 1 to 2 is: $$1, 2, 1$$ It contains (1, 2) and (2, 1).

With numbers from 1 to 3, it would look like something like this: $$1, 2, 3, 1, 2, 1, 3, 2, 1$$ It contains (1, 2, 3), (1, 3, 2), (2, 1, 3), …

Note: I'm not sure that this is the shortest list possible.

Is there any way to find the smallest list for numbers from 1 to $n$?

-

marked as duplicate by Ross Millikan, MJD, hardmath, Zev ChonolesJun 25 '12 at 22:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

– leonbloy Jun 25 '12 at 14:08

2 Answers

You are looking for de Bruijn sequences. That search term should find you what you want.

-
Not quite. In de Bruijn sequences every possible word of length $n$ occurs as subword, here only permutations (words without repetition) are considered. The "obvious lower bound" $n!+(n-1)$ cannot always be attained here, for instance a word of length $8$ in $3$ letters of which any successive triplet is distinct can contain only $3$ distinct permutations. So indeed one needs length $9$ for $n=3$. – Marc van Leeuwen Jun 25 '12 at 13:23
+1 since your answer shows that there is probably no "trivial" answer and one has to dig a little deeper. – Simon Markett Jun 25 '12 at 13:27
@Marc, you're right. I read the question quickly and carelessly. – Gerry Myerson Jun 25 '12 at 13:33
-
The reference discusses a slightly different problem in which permutations are required to appear as subsequences, but not necessarily consecutive subsequences as is here the case. – hardmath Jun 25 '12 at 15:21