login
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.
11
11, 54, 285, 1731, 12145, 97196, 874809, 8748145, 96229661, 1154756010, 15011828221, 210165595199, 3152483928105, 50439742849816, 857475628447025, 15434561312046621, 293256664928885989, 5865133298577719990, 123167799270132120021, 2709691583942906640715, 62322906430686852736721
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. Pre-fascicle 2B, A draft of section 7.2.1.2: Generating all permutations.
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.
FORMULA
a(3) = 11; a(n) = n*a(n-1) + n*(n+1)/2.
a(n) = 2*n! - 1 + A079750(n) + A079753(n).
For n>=3, a(n)=floor(c*n!-(n-3)/2) where c = lim_{n->oo} a(n)/n! = 2.4107560760219... - Benoit Cloitre; c=3*e/2-5/3 - Guido Dhondt (dhondt(AT)t-online.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
(PARI) a079884(nmax) = {my(a=vector(nmax)); a[3]=11; for(k=4, nmax, a[k]=k*a[k-1]+k*(k+1)/2); a[3..nmax]} \\ Hugo Pfoertner, Jun 05 2024
CROSSREFS
Partial counts given in A079750, A079753.
Number of index tests: A079885.
Sequence in context: A110159 A309921 A061983 * A200172 A348025 A050900
KEYWORD
easy,nonn
AUTHOR
Hugo Pfoertner, Jan 12 2003
STATUS
approved