The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

Nijenhuis and Wilf: Combinatorial Algorithms


Nijenhuis and Wilf's Combinatorial Algorithms, published by Academic Press in 1978, specializes in algorithms for constructing basic combinatorial objects such as permutations, subsets, and partitions; both randomly and sequentially. Such algorithms are often very short but hard to locate and usually are surprisingly subtle. Fortran programs for all of the algorithms are provided, as well as a discussion of the theory behind each of them. The programs are usually short enough that it is reasonable to translate directly into a more modern programming language, as I did with many of them in writing Combinatorica.

Descriptions of more recent algorithms for several problems, without code, are provided in Wilf's Combinatorial Algorithms, an update, published by SIAM in 1989.

These programs are now available here on our algorithm repository WWW site. We tracked them down from Neil Sloane, who had them on a magnetic tape where the authors did not! In their book, Nijenhuis and Wilf set the proper standard of statistically testing the output distribution of each of the random generators to establish that they really appear uniform. We encourage you to do the same before using these programs to verify that nothing has been lost in transit.


  • Download Files (local site)
  • Herbert Wilf's Home Page
  • Site to download the textbook

    Problem Links

      
    Generating Partitions (8)
      
    Generating Permutations (8)
      
    Generating Subsets (8)
      
    Determinants and Permanents (5)
      
    Generating Graphs (4)
      
    Hamiltonian Cycle (4)
      
    Eulerian Cycle / Chinese Postman (3)
      
    Network Flow (3)
      
    Vertex Coloring (3)
      
    Connected Components (2)
      
    Minimum Spanning Tree (2)
      
    Sorting (2)



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