5
$\begingroup$

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

  • 4
    dup? http://math.stackexchange.com/questions/15510/what-is-the-shortest-string-that-contains-all-permutations-of-an-alphabet2012-06-25

2 Answers 2

3

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

  • 1
    @Marc, you're right. I read the question quickly and carelessly.2012-06-25
1

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

  • 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.2012-06-25