|
Search: id:A079884
|
|
|
| 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. |
|
+0
11
|
|
| 11, 54, 285, 1731, 12145, 97196, 874809, 8748145, 96229661, 1154756010, 15011828221, 210165595199, 3152483928105, 50439742849816, 857475628447025, 15434561312046621, 293256664928885989, 5865133298577719990
(list; graph; listen)
|
|
|
OFFSET
|
3,1
|
|
|
COMMENT
|
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
|
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
|
|
PROGRAM
|
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: A059135 A110159 A061983 this_sequence A050900 A047649 A010927
Adjacent sequences: A079881 A079882 A079883 this_sequence A079885 A079886 A079887
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Hugo Pfoertner (hugo(AT)pfoertner.org), Jan 12 2003
|
|
|
Search completed in 0.002 seconds
|
