I've found an old (1978) FREE book, described how permanent algorithm was designed.
Combinatorial Algorithms for computers and calculators, 2nd edition, by Herbert S. Wilf, Albert Nijenhuis
Chapter 28, Computation of the Permanent Function Wrote:Observe that a direct application of (3) to an nxn matrix would require about n * n! operations
for the calculation of per(A). We reduce this labor in three steps.
(1) A method due to Ryser evaluates per(A) in about (n^2/2) * 2^n operations.
It requires an average of n^2/2 calculations for each of the 2^n subsets of {1,2,...,n}.
Ryser’s method is derived below and appears in Eqs. (17) and (18).
(2) We reduce the above by a factor of 2 by a method which makes it necessary to process
only the subsets of {1,2,...,n-1}. Thus in Eq. (24) we do about n^2/2 calculations for
each of the 2^(n-1) subsets of {1,2,... , n-1]}, or (n^2/4) * 2^n operations altogether.
(3) A further reduction by a factor of n/2 is accomplished by arranging the sequence of subsets
so as to follow a Hamilton walk on an (n-1)-cube (see Chapter 1), If this is done, only a slight
change in the calculation for a set S will yield the result of the calculation for the successor of S.
In this way, our final algorithm PERMAN does about n calculations for each of the 2^(n-1)
subsets of {1,2,...,n-1}, for a total of n * 2^(n-1) operations (multiplication and addition)
to compute the permanent of an nxn matrix.
Search
Member List
Calendar
Help
