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
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
KEYWORD
nonn
AUTHOR
Joerg Arndt, May 28 2011
STATUS
approved