A191246 - OEIS

%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