This code, written by Eric Michael Ryckman, is a realization of the algorithm suggested in The distance approach to approximate combinatorial counting by A. Samorodnitsky and A. Barvinok. Given an nxn matrix A of 0's and 1's, the algorithm interprets the permanent of A as the number of perfect matchings in a bipartite graph G encoded by A. The set M of all perfect matchings in G is embedded into a Boolean cube Cm={0,1}m (the algorithm tries to minimize the dimension m of the cube). Then the algorithm computes (approximately) the average Hamming distance from a point in Cm to the set of perfect matchings in G. The distance is computed by averaging distances to M from a number of randomly sampled points in the cube Cm. The number of random points to be sampled is determined by the user and our experience shows that relatively few points are needed to achieve a reasonably high precision (generally, we seem to have to sample much fewer points than suggested by theoretical bounds of the paper). For each particular point, the distance to the set of perfect matchings M is computed by solving an appropriate Assignment Problem. To solve the Assignment problem, with a kind permission of the authors, we use the code of R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse assignment problem, Computing, 38 1987, 325--340. Based on the average distance from a random point x in the Boolean cube Cm to the set of perfect matchings M in G, the algorithm provides a lower and an upper bound for the logarithm of the cardinality of M, which is equal to the logarithm of the permanent of the input matrix A. The bounds are best possible in the following sense: if for some set M of points in the cube Cm (not necessarily the set of perfect matchings in a graph) the only information available is the average Hamming distance from a random point x to M, one can't provide better bounds. Quite possibly, the set of perfect matchings in a graph has some special metric properties which we don't know how to use yet. In any case, the algorithm outputs also the average of the lower and the upper bounds and it has been our observation that in many cases the true value of log2 per A is close to that average. The input matrix A should be stored in a file. It can be typed using any text editor line by line with spaces between entries, such as
0 1 1 0 1
1 0 1 1 0
0 1 0 1 1
1 1 0 0 1
1 1 1 1 1
The algorithm seems to be extremely fast, being able to handle 200x200 matrices in a matter of seconds. The produced permanent bounds are pretty crude, yet often non-trivial (to get interesting results one should apply the algorithm to matrices of a large size).