The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.3.4 Generating Permutations

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: An integer n.

Problem: Generate (1) all, or (2) a random, or (3) the next permutation of length n.

Excerpt from The Algorithm Design Manual: Fundamental to any permutation-generation algorithm is a notion of order, the sequence in which the permutations are constructed, from first to last. The most natural generation order is lexicographic, the order they would appear if they were sorted numerically. Lexicographic order for $n=3$ is $\{1,2,3\}$, $\{1,3,2\}$, $\{2,1,3\}$, $\{2,3,1\}$, $\{3,1,2\}$, and finally $\{3,2,1\}$. Although lexicographic order is aesthetically pleasing, there is often no particular reason to use it. For example, if you are searching through a collection of files, it does not matter whether the filenames are encountered in sorted order, so long as you search through all of them. Indeed, nonlexicographic orders lead to faster and simpler permutation generation algorithms.

There are two different paradigms for constructing permutations: ranking/unranking and incremental change methods. Although the latter are more efficient, ranking and unranking can be applied to solve a much wider class of problems, including the other combinatorial generation problems.


Implementations

  • Standard Template library in C++ form SGI (C++) (rating 10)
  • C.A.G.E.S. (C) (rating 9)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 8)
  • FFT - Fast Fourier Transform (C,FORTRAN) (rating 8)
  • Frank Ruskey's Combinatorial Generation Resources (C,Pascal) (rating 8)
  • Combinatorica (Mathematica) (rating 7)

  • Recommended Books

    The Art of Computer Programming, Volume 4 Fascicle 2: Generating All Tuples and Permutations by D. E. Knuth Tables of Random Permutations by L. E. Moses and R. V. Oakford

    Related Links

  • The fxt demos: permutations

    Related Problems


      
    Calendrical Calculations
      
    Generating Graphs
      
    Generating Partitions
      
    Generating Subsets
      
    Random Number Generation



    This page last modified on 2008-07-10 .
    www.algorist.com