Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #13 Jun 05 2024 10:02:15
%S 11,54,285,1731,12145,97196,874809,8748145,96229661,1154756010,
%T 15011828221,210165595199,3152483928105,50439742849816,
%U 857475628447025,15434561312046621,293256664928885989,5865133298577719990,123167799270132120021,2709691583942906640715,62322906430686852736721
%N 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.
%C 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).
%D 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.
%D 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.
%H Hugo Pfoertner, <a href="https://www.randomwalk.de/sequences/lpgcount.txt">FORTRAN program for lexicographic permutation generation</a>.
%H J. P. N. Phillips, <a href="https://doi.org/10.1093/comjnl/10.3.306">Algorithm 28 from Algorithms supplement</a>.
%F a(3) = 11; a(n) = n*a(n-1) + n*(n+1)/2.
%F a(n) = 2*n! - 1 + A079750(n) + A079753(n).
%F 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
%e 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.
%o (Fortran) Program available at Pfoertner link
%o (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
%Y Partial counts given in A079750, A079753.
%Y Number of index tests: A079885.
%Y Cf. A000217, A000142, A038155, A038156.
%K easy,nonn
%O 3,1
%A _Hugo Pfoertner_, Jan 12 2003