[seqfan] Re: A007489 and strings containing all permutations
arndt at jjj.de
Sat Feb 20 11:59:33 CET 2010
The problem appears to be (related to) an instance of a
"universal cycle", please check the following:
Frank Ruskey, Aaron Williams:
"An explicit universal cycle for the (n-1)-permutations of an n-set",
ACM Transactions on Algorithms, (2008).
This is ref  on p.890 (end section 39.5) of the fxtbook:
We note that there are several ways to generalize the idea of the De
Bruijn cycles to universal cycles for combinatorial objects as
described in . An explicit construction for universal cycles for
permutations is given in . The problem of finding a rectangular
pattern such that all different patterns of given size appear is
discussed in . De Bruijn sequences for words with forbidden
substrings are discussed in .
The construction you are giving (on stackoverflow) is
very similar to Trotter's method (you do not zig-zag the
new element, instead you always move it from right to left).
See also (fxtbook) p.267ff, section 10.11.1
(the earliest ref I found for this order is
Eugen Netto: "Lehrbuch der Combinatorik", 1901).
* Jason Orendorff <jason.orendorff at gmail.com> [Feb 20. 2010 11:35]:
> I think A007489 gives the length of the shortest string of n symbols that
> contains all n! permutations of those n symbols as contiguous substrings. The
> first 4 such strings are: 1, 121, 123121321, 123412314231243121342132413214321,
> having lengths 1, 3, 9, 33. Neat, huh? It seems interesting enough to go in the
> entry, if it's true. I think it is; a summary of my argument is posted here:
Note this is
> Unfortunately, I can't find a reference for this. All the papers I've
> been able to
> find are about a different problem, described here:
> Surely this is known. Can anyone provide the reference?
> Thanks for your time.
> Jason Orendorff
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan