login
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
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
Joerg Arndt, Matters Computational (The Fxtbook), section 10.8 "Star-transposition order", pp.257-258
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 );
}
vector(5!, n, a(n-1) ) \\ Joerg Arndt, Dec 28 2023
CROSSREFS
Cf. A123400 (giving the nonzero position in "swap" in example).
Sequence in context: A336820 A099173 A293377 * A289251 A353174 A233292
KEYWORD
nonn
AUTHOR
Joerg Arndt, Apr 25 2009
STATUS
approved