

A079884


Number of comparisons 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.


10



11, 54, 285, 1731, 12145, 97196, 874809, 8748145, 96229661, 1154756010, 15011828221, 210165595199, 3152483928105, 50439742849816, 857475628447025, 15434561312046621, 293256664928885989, 5865133298577719990
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,1


COMMENTS

The method generates all permutations in lexicographic order. It is described in the answer to Exercise 1, Section 7.2.1.2 of Knuth's The Art of Computer Programming Vol. 4. The description is based on the Algol procedure NEXTPERM by J.P.N.Phillips. The operation counts were determined with a FORTRAN subroutine LPG. To create all permutations of n distinct elements the number of comparisons between the array elements approaches 2.410756*n! for large n (e.g. n>8)


REFERENCES

D. E. Knuth: The Art of Computer Programming, Volume 4, Combinatorial Algorithms, Volume 4A, Enumeration and Backtracking. Prefascicle 2B, A draft of section 7.2.1.2: Generating all permutations. Available online; see link.
J. P. N. Phillips: "Algorithm 28, PERMUTATIONS OF THE ELEMENTS OF A VECTOR IN LEXICOGRAPHIC ORDER" The Computer Journal, Volume 10, Issue 3: November 1967. (Algorithms supplement), page 311. See link.


LINKS

Table of n, a(n) for n=3..20.
D. E. Knuth, TAOCP Vol. 4, Prefascicle 2b (generating all permutations).
Hugo Pfoertner, FORTRAN program for lexicographic permutation generation.
J. P. N. Phillips, Algorithm 28 from Algorithms supplement.


FORMULA

a(3)=11 a(n) = n*a(n1) + n*(n+1)/2 a(n) = 2*n!  1 + A079750(n) + A079753(n)
For n>=3, a(n)=floor(c*n!(n3)/2) where c=limit n>infinity a(n)/n!=2.4107560760219...  Benoit Cloitre; c=3*e/25/3  Guido Dhondt (dhondt(AT)tonline.de), Jan 20 2003


EXAMPLE

The "streamlined" permutation algorithm L' needs fewer comparisons a(n) than the original Algorithm L, for which the number of required comparisons between the elements to be permuted is given by A038156(n) for step L2 and A038155(n) for step L3. A038156(3)+A038155(3)=9+6=15 > a(3)=11 A038156(4)+A038155(4)=40+30=70 > a(4)=54 A038156(10)+A038155(10)=6235300+4932045=11167345 > a(10)=8748145


PROG

FORTRAN program available at Pfoertner link


CROSSREFS

Cf. A000142, partial counts given in A079750, A079753. Number of index tests: A079885.
Cf. A038155, A038156.
Sequence in context: A110159 A309921 A061983 * A200172 A050900 A246406
Adjacent sequences: A079881 A079882 A079883 * A079885 A079886 A079887


KEYWORD

easy,nonn


AUTHOR

Hugo Pfoertner, Jan 12 2003


STATUS

approved



