[seqfan] Re: A007489 and strings containing all permutations

[Joerg Arndt]

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/