[seqfan] Re: A007489 and strings containing all permutations
Joerg Arndt
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).
URL: http://www.cs.uvic.ca/~ruskey/Publications/
This is ref [275] 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 [96]. An explicit construction for universal cycles for
permutations is given in [275]. The problem of finding a rectangular
pattern such that all different patterns of given size appear is
discussed in [174]. De Bruijn sequences for words with forbidden
substrings are discussed in [238].
-------------------------
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).
cheers, jj
* 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:
>
> http://bit.ly/9h917c
Note this is
http://stackoverflow.com/questions/2253232/generate-sequence-with-all-permutations/2274978#2274978
>
> 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:
>
> http://garden.irmacs.sfu.ca/?q=op/smallest_universal_supersequence
>
> 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
mailing list