A191246 Length of prefix cyclically shifted with permutations in cool-lex ordering.

0, 2, 3, 3, 2, 3, 4, 2, 4, 2, 3, 3, 2, 3, 4, 3, 2, 4, 2, 3, 3, 2, 3, 4, 5, 2, 3, 3, 2, 3, 5, 2, 3, 3, 2, 3, 4, 2, 4, 2, 3, 3, 2, 3, 4, 3, 2, 4, 2, 3, 3, 2, 3, 4, 5, 2, 4, 2, 3, 3, 2, 3, 5, 2, 3, 3, 2, 3, 4, 2, 4, 2, 3, 3, 2, 3, 4, 3, 2, 4, 2, 3, 3, 2, 3, 4, 5, 3, 2, 4, 2, 3, 3, 2, 3, 5, 2, 3, 3, 2, 3, 4, 2, 4, 2, 3, 3, 2, 3, 4, 3, 2, 4, 2, 3, 3, 2, 3, 4, 5, 6, 2

Offset

0,2

Comments

Start with the identical permutation [0,1,2,...,n-1] and obtain the next permutation by cyclically shifting the prefix of length a(n) (n>=1) by one position to the right, see example. For every n the ordering is cyclic: the first permutation is a cyclic shift of the last when taking the prefix to be the full length n (instead of n+1 as the sequence gives).

References

Aaron Williams, Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts, ACM-SIAM Symposium on Discrete Algorithms (SODA09), (2009), see link.

Links

Table of n, a(n) for n=0..121.

SODA 2009 proceedings with Williams' paper: SIAM: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms.

Example

Permutations of 4 elements, via cyclic prefix shifts.
The first permutation is the one used in the original algorithm, followed by the length of the prefix shifted, the second is the permutation starting with identity:
   0:  [ 0 3 2 1 ]  -  [ 0 1 2 3 ]
   1:  [ 3 0 2 1 ]  2  [ 1 0 2 3 ]
   2:  [ 2 3 0 1 ]  3  [ 2 1 0 3 ]
   3:  [ 0 2 3 1 ]  3  [ 0 2 1 3 ]
   4:  [ 2 0 3 1 ]  2  [ 2 0 1 3 ]
   5:  [ 3 2 0 1 ]  3  [ 1 2 0 3 ]
   6:  [ 1 3 2 0 ]  4  [ 3 1 2 0 ]
   7:  [ 3 1 2 0 ]  2  [ 1 3 2 0 ]
   8:  [ 0 3 1 2 ]  4  [ 0 1 3 2 ]
   9:  [ 3 0 1 2 ]  2  [ 1 0 3 2 ]
  10:  [ 1 3 0 2 ]  3  [ 3 1 0 2 ]
  11:  [ 0 1 3 2 ]  3  [ 0 3 1 2 ]
  12:  [ 1 0 3 2 ]  2  [ 3 0 1 2 ]
  13:  [ 3 1 0 2 ]  3  [ 1 3 0 2 ]
  14:  [ 2 3 1 0 ]  4  [ 2 1 3 0 ]
  15:  [ 1 2 3 0 ]  3  [ 3 2 1 0 ]
  16:  [ 2 1 3 0 ]  2  [ 2 3 1 0 ]
  17:  [ 0 2 1 3 ]  4  [ 0 2 3 1 ]
  18:  [ 2 0 1 3 ]  2  [ 2 0 3 1 ]
  19:  [ 1 2 0 3 ]  3  [ 3 2 0 1 ]
  20:  [ 0 1 2 3 ]  3  [ 0 3 2 1 ]
  21:  [ 1 0 2 3 ]  2  [ 3 0 2 1 ]
  22:  [ 2 1 0 3 ]  3  [ 2 3 0 1 ]
  23:  [ 3 2 1 0 ]  4  [ 1 2 3 0 ]

Crossrefs

A191247 (first element).

Sequence in context: A308661 A286104 A137779 * A248222 A107918 A242392

Adjacent sequences: A191243 A191244 A191245 * A191247 A191248 A191249

Keyword

nonn

Author

Joerg Arndt, May 28 2011

Status

approved