Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

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.

4  
dup? math.stackexchange.com/questions/15510/… –  leonbloy Jun 25 '12 at 14:08

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
4  
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
1  
@Marc, you're right. I read the question quickly and carelessly. –  Gerry Myerson Jun 25 '12 at 13:33

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

share|improve this answer
1  
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

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