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)
Wilf's most relevant book Combinatorial Algorithms: An Update.
Files with driver programs and test data (local site)
Problem Links
Generating Subsets (8)
Generating Permutations (8)
Generating Partitions (8)
Hamiltonian Cycle (5)
Generating Graphs (4)
Determinants and Permanents (4)
Vertex Coloring (3)
Sorting (3)
Network Flow (3)
Minimum Spanning Tree (3)
Eulerian Cycle / Chinese Postman (3)
Connected Components (2)
Post comments
Read comments
View
the statistics for this
implementation
Bulletin Board
The Algorithm Design Manual.
Send us Mail
The Stony Brook Algorithm Repository -- go
to front page
This page last modified on Nov 2, 1999.