Nijenhuis and Wilf: Combinatorial Algorithms
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.
Link to Wilf's Home Page -- many interesting things
Download Files (local site)
Files with driver programs and test data (local site)
Problem Links
Generating Partitions (8)
Generating Permutations (8)
Generating Subsets (8)
Hamiltonian Cycle (5)
Determinants and Permanents (4)
Generating Graphs (4)
Eulerian Cycle / Chinese Postman (3)
Minimum Spanning Tree (3)
Network Flow (3)
Sorting (3)
Vertex Coloring (3)
Connected Components (2)
About the Book
Send us Mail
Go to Main Page
This page last modified on Apr 28, 1997.