login
A123400
Infinite string related to Ehrlich's swap method for generating permutations.
3
1, 2, 1, 2, 1, 3, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 1, 3, 2, 1, 2, 1, 2, 4, 3, 1, 3, 1, 3, 2, 1, 3, 1, 3, 1, 2, 3, 1, 3, 1, 3, 2, 1, 3, 1, 3, 1, 4, 2, 3, 2, 3, 2, 1, 3, 2, 3, 2, 3, 1, 2, 3, 2, 3, 2, 1, 3, 2, 3, 2, 3, 4, 1, 2, 1, 2, 1, 3, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 1, 3, 2, 1, 2, 1, 2, 4, 3, 1, 3, 1, 3, 2, 1, 3, 1
OFFSET
1,2
COMMENTS
In the successive permutations in star-transposition order a(n) is the position of the element swapped with the first element at step n; equivalently, the value swapped with 0 in the inverse permutation. - Joerg Arndt, Dec 25 2023
The first 24 values (plus 1, as [2, 3, 2, 3, 2, 4, 3, 2, 3, 2, 3, 4, 2, 3, 2, 3, 2, 4, 3, 2, 3, 2, 3, 5]) are given on the last page of the Kompel'makher/Liskovets reference. - Joerg Arndt, Jan 17 2024
REFERENCES
D. E. Knuth, TAOCP, Section 7.2.1.2.
LINKS
Joerg Arndt, Matters Computational (The Fxtbook), section 10.8 "Star-transposition order", pp.257-258.
V. L. Kompel'makher, V. A. Liskovets, Sequential generation of arrangements by a basis of transpositions, Cybernetics and Systems Analysis, vol. 11, no. 3, pp. 362-366, (1975).
EXAMPLE
permutation swap inverse permutation
0: [ 0 1 2 3 ] [ 0 1 2 3 ]
1: [ 1 0 2 3 ] (0, 1) [ 1 0 2 3 ]
2: [ 2 0 1 3 ] (0, 2) [ 1 2 0 3 ]
3: [ 0 2 1 3 ] (0, 1) [ 0 2 1 3 ]
4: [ 1 2 0 3 ] (0, 2) [ 2 0 1 3 ]
5: [ 2 1 0 3 ] (0, 1) [ 2 1 0 3 ]
6: [ 3 1 0 2 ] (0, 3) [ 2 1 3 0 ]
7: [ 0 1 3 2 ] (0, 2) [ 0 1 3 2 ]
8: [ 1 0 3 2 ] (0, 1) [ 1 0 3 2 ]
9: [ 3 0 1 2 ] (0, 2) [ 1 2 3 0 ]
10: [ 0 3 1 2 ] (0, 1) [ 0 2 3 1 ]
11: [ 1 3 0 2 ] (0, 2) [ 2 0 3 1 ]
12: [ 2 3 0 1 ] (0, 3) [ 2 3 0 1 ]
13: [ 3 2 0 1 ] (0, 1) [ 2 3 1 0 ]
14: [ 0 2 3 1 ] (0, 2) [ 0 3 1 2 ]
15: [ 2 0 3 1 ] (0, 1) [ 1 3 0 2 ]
16: [ 3 0 2 1 ] (0, 2) [ 1 3 2 0 ]
17: [ 0 3 2 1 ] (0, 1) [ 0 3 2 1 ]
18: [ 1 3 2 0 ] (0, 3) [ 3 0 2 1 ]
19: [ 2 3 1 0 ] (0, 2) [ 3 2 0 1 ]
20: [ 3 2 1 0 ] (0, 1) [ 3 2 1 0 ]
21: [ 1 2 3 0 ] (0, 2) [ 3 0 1 2 ]
22: [ 2 1 3 0 ] (0, 1) [ 3 1 0 2 ]
23: [ 3 1 2 0 ] (0, 2) [ 3 1 2 0 ]
CROSSREFS
Cf. A159880 (first element in successive permutations).
Sequence in context: A356233 A353382 A231719 * A232502 A288738 A214651
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Oct 15 2006
EXTENSIONS
More terms from Joerg Arndt, Apr 25 2009
STATUS
approved