login
A191246
Length of prefix cyclically shifted with permutations in cool-lex ordering.
2
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.
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
KEYWORD
nonn
AUTHOR
Joerg Arndt, May 28 2011
STATUS
approved