A079885 Number of index tests required to create all permutations of n distinct elements using the "streamlined" version of Algorithm L (lexicographic permutation generation) from Knuth's The Art of Computer Programming, Vol. 4, chapter 7.2.1.2.

0, 4, 29, 185, 1314, 10534, 94839, 948427, 10432748, 125193032, 1627509489, 22785132925

Offset

3,2

Comments

The required number of index tests (test for termination and test in the final reversion loop) becomes 0.2613625*n! for large n, if the test for n=3 is excluded. If n=3 is included the additionally required termination test adds n!/6 index comparisons, increasing the number of index comparisons to 0.428029*n! (63.8% more index comparisons).

The corresponding number of index tests needed by the "pure" Algorithm L is given by A038156(n)+A080048(n), which is 12.478..*a(n) for large n.

References

For references and corresponding links see under A079884

Links

Table of n, a(n) for n=3..14.

Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.

Formula

a(3)=0, a(n)=n*a(n-1)+1+(n-1)*floor((n-1)/2) for n>=4 a(n) = A079751(n) + A079755(n)

For n>=3 a(n)=floor(c*n!-(n-3)/2) where c=limit n-->infinity a(n)/n!= 0.261362463274289013838... - Benoit Cloitre, Jan 20 2003

In closed form, c = 3*exp(1)/2 + exp(-1)/2 - 4. - Vaclav Kotesovec, Mar 18 2014

Prog

FORTRAN program available at link

Crossrefs

Cf. A000142, partial counts given in A079751, A079755. Number of element comparisons: A079884.

Cf. A038156, A080048.

Sequence in context: A353818 A198794 A258416 * A364404 A121191 A129587

Adjacent sequences: A079882 A079883 A079884 * A079886 A079887 A079888

Keyword

nonn

Author

Hugo Pfoertner, Jan 13 2003

Status

approved