|
%I #9 Mar 30 2012 17:36:33
%S 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,
%T 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,
%U 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
%N Length of prefix cyclically shifted with permutations in cool-lex ordering.
%C 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).
%D 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.
%H SODA 2009 proceedings with Williams' paper: <a href="http://www.siam.org/proceedings/soda/2009/soda09.php">SIAM: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms</a>.
%e Permutations of 4 elements, via cyclic prefix shifts.
%e 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:
%e 0: [ 0 3 2 1 ] - [ 0 1 2 3 ]
%e 1: [ 3 0 2 1 ] 2 [ 1 0 2 3 ]
%e 2: [ 2 3 0 1 ] 3 [ 2 1 0 3 ]
%e 3: [ 0 2 3 1 ] 3 [ 0 2 1 3 ]
%e 4: [ 2 0 3 1 ] 2 [ 2 0 1 3 ]
%e 5: [ 3 2 0 1 ] 3 [ 1 2 0 3 ]
%e 6: [ 1 3 2 0 ] 4 [ 3 1 2 0 ]
%e 7: [ 3 1 2 0 ] 2 [ 1 3 2 0 ]
%e 8: [ 0 3 1 2 ] 4 [ 0 1 3 2 ]
%e 9: [ 3 0 1 2 ] 2 [ 1 0 3 2 ]
%e 10: [ 1 3 0 2 ] 3 [ 3 1 0 2 ]
%e 11: [ 0 1 3 2 ] 3 [ 0 3 1 2 ]
%e 12: [ 1 0 3 2 ] 2 [ 3 0 1 2 ]
%e 13: [ 3 1 0 2 ] 3 [ 1 3 0 2 ]
%e 14: [ 2 3 1 0 ] 4 [ 2 1 3 0 ]
%e 15: [ 1 2 3 0 ] 3 [ 3 2 1 0 ]
%e 16: [ 2 1 3 0 ] 2 [ 2 3 1 0 ]
%e 17: [ 0 2 1 3 ] 4 [ 0 2 3 1 ]
%e 18: [ 2 0 1 3 ] 2 [ 2 0 3 1 ]
%e 19: [ 1 2 0 3 ] 3 [ 3 2 0 1 ]
%e 20: [ 0 1 2 3 ] 3 [ 0 3 2 1 ]
%e 21: [ 1 0 2 3 ] 2 [ 3 0 2 1 ]
%e 22: [ 2 1 0 3 ] 3 [ 2 3 0 1 ]
%e 23: [ 3 2 1 0 ] 4 [ 1 2 3 0 ]
%Y A191247 (first element).
%K nonn
%O 0,2
%A _Joerg Arndt_, May 28 2011
|
