# 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

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