login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. Pre-fascicle 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, Pre-fascicle 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(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=limit n->infinity 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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 28 14:19 EDT 2021. Contains 346335 sequences. (Running on oeis4.)