|
|
A159880
|
|
Infinite string related to Ehrlich's swap method for generating permutations.
|
|
4
|
|
|
0, 1, 2, 0, 1, 2, 3, 0, 1, 3, 0, 1, 2, 3, 0, 2, 3, 0, 1, 2, 3, 1, 2, 3, 4, 0, 1, 4, 0, 1, 2, 4, 0, 2, 4, 0, 1, 2, 4, 1, 2, 4, 0, 1, 2, 0, 1, 2, 3, 4, 0, 3, 4, 0, 1, 3, 4, 1, 3, 4, 0, 1, 3, 0, 1, 3, 4, 0, 1, 4, 0, 1, 2, 3, 4, 2, 3, 4, 0, 2, 3, 0, 2, 3, 4, 0, 2, 4, 0, 2, 3, 4, 0, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4, 1, 2, 4, 1, 2, 3, 4, 1, 3, 4, 1, 2, 3, 4, 2, 3, 4, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the position of the zero in the inverse permutation of the one generated by "Algorithm E" given in D. E. Knuth, TAOCP, Section 7.2.1.2.
Alternatively, the first element in the permutation (see example).
Starting with the identical permutation, the list of permutations in star-transposition order can be generated by swapping p(a(n)) with p(a(n+1)). - Joerg Arndt, Dec 25 2023
|
|
REFERENCES
|
D. E. Knuth, TAOCP, Section 7.2.1.2.
|
|
LINKS
|
|
|
FORMULA
|
a(k!) = k (for k>=1) and a(j) < k for j<k!. [Joerg Arndt, Mar 20 2014]
|
|
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 ]
|
|
PROG
|
(PARI)
ss( n ) =
{
my(k, f, nf, v);
f = 1; k = 2; /* f==(k-1)! */
nf = f * k; /* nf==k! */
v = vector(n);
for ( p=1, #v-1,
if ( p>=nf, f=nf; k+=1; nf*=k );
v[p+1] = (v[p-f+1]-1) % k;
);
return(v);
}
ss( 5! )
(PARI) \\ individual terms:
a( n ) =
{
my( ret = 0, k = 0 );
while ( n != 0 ,
k += 1;
my( d = n % (k+1) );
n \= (k+1);
ret = (ret - d) % (k+1);
);
return( ret );
}
|
|
CROSSREFS
|
Cf. A123400 (giving the nonzero position in "swap" in example).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|