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 Chonoles Jun 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.


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

  • 4
    $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen Jun 25 '12 at 13:23
  • $\begingroup$ +1 since your answer shows that there is probably no "trivial" answer and one has to dig a little deeper. $\endgroup$ – Simon Markett Jun 25 '12 at 13:27
  • 1
    $\begingroup$ @Marc, you're right. I read the question quickly and carelessly. $\endgroup$ – Gerry Myerson Jun 25 '12 at 13:33

A reference: http://people.inf.ethz.ch/zeugen/papers/zal_ipl11_perms.pdf

  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Jun 25 '12 at 15:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.