A159880 Infinite string related to Ehrlich's swap method for generating permutations.

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, Table of n, a(n) for n = 0..5039

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

Adjacent sequences: A159877 A159878 A159879 * A159881 A159882 A159883

Keyword

nonn

Author

Joerg Arndt, Apr 25 2009

Status

approved