Programs to Read
I write lots of
CWEB programs, primarily for my own
edification. If there is sufficient interest, I'll make a large subset
of them available via the Internet. For now, I'm listing only a few.
The first two show (by quite different methods) that exactly 2,432,932
knight's tours are unchanged by 180-degree rotation of the chessboard.
The third was used to compute some of the tables in
Axioms and Hulls
that several people have asked about.
The fourth was used in one of my otherwise unpublished lectures in the
Computer Musings series. The next few were
requested by members of the Academy of Recreational Mathematicians
in Japan. And so on.
Note: Many of my programs, including the first two samples, use
the conventions and library of
The Stanford GraphBase.
- SHAM
- Enumerates symmetrical Hamiltonian cycles (December 1992)
- OBDD
- Enumerates perfect matchings of bipartite graphs (May 1996)
- REFLECT; also a
change file for REFLECT
- Enumerates equivalence classes of reflection networks, aka CC systems
(January 1991)
- HULL,
HULLS,
HULLT,
HULLTR
- Programs used as examples in
Axioms and Hulls; also change files for
ngons,
square deletion, and
uniform input distribution
- TCALC
- Interactively calculates with humungous numbers (December 1994)
- DECAGON; also a
change file for DECAGON (stars);
also a
change file for DECAGON (color);
also a
change file for DECAGON (color
stars)
- Packs golden triangles into decagons, stars, pentagons, etc.
(September 1994)
- ANTISLIDE; also a
change file for ANTISLIDE
- Finds solutions to Strijbos's antisliding block puzzle (November 1994)
- ANTISLIDE3
- Improved version of ANTISLIDE, finds all nonisomorphic solutions (December 1996)
- SETSET
- Enumerates nonisomorphic unplayable hands in the game of SET® (February 2001)
- SETSET-ALL
- Improvement of SETSET---fifty times faster---when a huge automorphism group is considered (March 2001)
- SETSET-RANDOM
- Simple Monte Carlo routine to validate the previous two programs (March 2001)
- SLIDING
- Finds solutions to sliding block puzzles (November 2001)
- STRAIGHTEN
-
- Computes irreducible matrix representations of permutations (August 2003)
- DOMINATION
-
- Computes the covering relation for an interesting partial ordering
of multiset permutations (August 2003)
- FOG2MF
- Rudimentary conversion from Fontographer to METAFONT (August 1996)
- LAGFIB
- Calculator of weights related to the random number generator below (July 1997)
- GARSIA-WACHS
- Simple implementation of Algorithm 6.2.2G (January 1998, revised September 2004)
- HALFTONE
- Preprocessor for typeset halftones; also example input files
lisa-64,
lisa-rot,
lisa-128,
lin-64,
lin-rot,
lin-128,
lib-64,
lib-rot,
lib-128 (June 1998)
- DOT-DIFF
- Preprocessor for halftones by dot diffusion; also an example input file
lisa-512,
and a change file for EPS output
(June 1998)
- TOGPAP
- Generates examples of halftones for paper P116 on dot diffusion (June 1998)
- DANCE,
POLYOMINOES,
POLYIAMONDS,
POLYSTICKS,
QUEENS
- Generates examples for paper P159 on dancing links (July 1999); and another,
SUDOKU (February 2005); also a
change file for Monte Carlo estimates (corrected 25 Jan 07)
- GDANCE,
MACMAHON-TRIANGLES-SYM-TILE,
XGDANCE,
GDANCE-CUTOFF
- Experimental extensions of the Dancing Links algorithm (November 2000)
- HAMDANCE
- A dancing-link-based program for Hamiltonian circuits (May 2001),
which you might
want to compare to the more traditional algorithm of
HAM
- POLYNUM,
POLYSLAVE, and their change files
POLYNUM-RESTART and
POLYSLAVE-RESTART for long runs
- Enumerates polyominoes with Iwan Jensen's algorithm, thousands of times
faster than previous approaches (but is a memory hog); also
notes from Jensen about potential further
improvements and the probable value of t(48); also a MetaPost source
file polyomino.mp to make an illustration
for the documentation of both POLYNUM and a now-obsolete program
POLYENUM
- ADVENT
- The original Crowther/Woods Adventure game, Version 1.0, translated into CWEB form; I offer $2.56 to the first finder of any error in this beta-test version (improved version of 28 October 2003)
- ROST
- Monte Carlo confirmation of exercise 5.1.4--40 (October 1998)
- RAN-PRIM
- Monte Carlo exploration of exercise 5.3.4--40 (October 1998)
- STRONGCHAIN
- finds shortest strong addition chains, also called Lucas chains or
Chebyshev chains (August 2000)
- KODA-RUSKEY
- A fascinating generalized reflected Gray-code generator (new version, June 2001)
- LI-RUSKEY
- An even more fascinating, massive generalization of the previous
program (June 2001); also a PostScript illustration
li-ruskey.1 made by the
MetaPost source file li-ruskey.mp
- SPIDERS
- A further improvement to the previous two (December 2001),
and its PostScript illustration
deco.5
- TOPSWOPS and
TOPSWOPS-FWD
- Two ways to find the longest plays of John Conway's "topswops" game
(August 2001)
- POSETS0 and
POSETS
- Two programs to evaluate the numbers in Sloane's sequence A006455, formerly M1805 (December 2001)
- ERECTION
-
- The algorithms described in my paper ``Random Matroids'' (March 2003)
- UNAVOIDABLE
-
- A longest word that avoids all n-letter subwords in an interesting minimal
set constructed by Champernaud, Hansel, and Perrin (July 2003)
- UNAVOIDABLE2
-
- A longest word that avoids all n-letter subwords in an interesting minimal
set constructed by Mykkeltveit (August 2003)
- GRAYSPAN,
SPSPAN,
GRAYSPSPAN,
and a MetaPost source file for SPSPAN,
plus an auxiliary program SPGRAPH
- Three instructive ways to generate all spanning trees of a graph (August 2003)
- SAND
- A hastily written program to experiment with sandpiles as in exercise 7.2.1.6--103
(December 2004)
-
ZEILBERGER,
FRANÇON,
VIENNOT,
an explanatory introduction,
and a MetaPost source file for VIENNOT
- Three Catalan bijections related to Strahler numbers, pruning orders,
and Kepler towers (February 2005)
- LINKED-TREES
- An amazingly short program to generate linked trees with given node degrees (March 2005)
- VACILLATE
- A program to experiment with set partitions and vacillating tableau loops (May 2005)
- EMBED
- An algorithm of Hagauer, Imrich, and Klavžar to embed a median
graph in a hypercube (June 2005)
- LP
- An expository implementation of linear programming (August 2005)
- HORN-COUNT
- A program to enumerate Horn functions; also a change file
krom-count.ch, which adapts
it to Krom functions (aka 2SAT instances) (August 2005)
- 15PUZZLE-KORF0 and
15PUZZLE-KORF1
- Two programs to solve 15-puzzle problems rather fast (but not state-of-the-art) (August 2005)
- ACHAIN0,
ACHAIN1,
ACHAIN2,
ACHAIN3,
ACHAIN4, and
ACHAIN-ALL
- A series of programs to find minimal addition chains (September 2005),
plus a trivial auxiliary program
ACHAIN-DECODE.
- HYPERBOLIC
and a MetaPost source file for HYPERBOLIC
- A program that analyzes and helps to draw the hyperbolic plane tiling
made from 36-45-90 triangles (October 2005)
- BOOLCHAINS
- A suite of programs that find the complexity of almost all Boolean functions of five variables (December 2005)
- FCHAINS4X and
and a change file for don't-cares
- Programs for interactive minimization of multiple-output 4-input Boolean functions
using the `greedy footprint' method (February 2006)
- TICTACTOE, a gzipped tar file tictactoe.tgz
- Various programs used when preparing the tic-tac-toe examples in Section 7.1.2 (March 2006)
- PRIME-SIEVE and its much faster (but more complex) cousin
PRIME-SIEVE-SPARSE, plus a change file
PRIME-SIEVE-BOOT to compute several million
primes to be input by the other programs
- Programs for the segmented sieve of Eratosthenes on 64-bit machines, tuned for
finding all large gaps between primes in the neighborhood of 10^18 (May 2006)
- MAXCLIQUES
- The Moody--Hollis algorithm for listing all maximal cliques, all maximal independent sets,
and/or all minimal vertex covers (July 2006)
- ULAM and a
change file for 64-bit machines
- Short program to compute the Ulam numbers 1, 2, 3, 4, 6, ... (September 2006)
- BDD14
- Bare-bones BDD package that I used for practice when preparing Section 7.1.4 of TAOCP
(May 2008)
- BDD12
- A program to find the best and worst variable orderings for a given BDD
- YPLAY
- Simple program to play with Schensted's Y function (April 2008)
Programs in languages other than CWEB:
- RANARRAY
- Portable random number generator recommended in Seminumerical Algorithms,
3rd edition,
new and improved version
(last updated November 2002)
- tpk.i
- The
TPK algorithm in
INTERCAL; also some
sample input and its
corresponding output
- SGBFIG
- MetaPost
sources for the illustrations in
The Stanford GraphBase (1994)
- color-mode.el
- An experimental line-oriented color mode for Emacs (August 2000)
- Sample Fvwm2 Config File
- The emacs-oriented desktop layouts I use on my home computer to write
books;
these also need icons
zero.xpm,
one.xpm,
two.xpm,
three.xpm (May 2000, updated December 2007)
- my6x13.bdf and
my6x13B.bdf
- TeX-oriented bitmap fonts that I use for text editing with emacs
- DonKeys.keylayout and
DonKeysExtended.keylayout
- Custom keyboards for my Macintoshes -- more logical and efficient
because they switch () with [], also + with = (April 2005); use them with
DonKeys.icns and
DonKeysExtended.icns
- texmf-sail.tgz
- source code listings for the first implementations of TeX and METAFONT (late 1970s)
- tex.web
- TeX version -0.25 as it existed when I gave
twelve lectures on the internal details of TeX82
in July 1982
Don Knuth's home page