Uses the Ryser Formula to calculate the permanent of a matrix. It is O((n^2)(2^n)) which is much faster than the naive algorithm O(n!n). The determinate of a matrix is defined as the analog of determinant where the signs of
each term in summation was removed.
For an empty matrix, I believe that the permanent is equal to one, which coincides with the determinant of an empty matrix.
So an if statement is needed, for example:
y=1; %the permanent of an empty matrix is one.
%% insert original permanent code using the Ryser formula
serious troubles with accuracy!!!
I've found that Ryser's algorithm has numerical accuracy issues in floating point due to the large-valued products (of row sums). They are often much, much larger than the final result, drastically increasing the chances intermediate rounding. Try the following test. Compute permanentRyser(ones(15,15)) - factorial(15). It should be zero.
I am proposing a Ryser absolute +/-accuracy estimate of approximately accu = prod(sum(A,2)) *10 /2^53, for non-negative matrices.
Nicely done. I sped it up by x4 using Gray coding. See my version here: http://www.mathworks.com/matlabcentral/fileexchange/52739-matrix-permanent-using-fast-ryser-algorithm
Inspired by: Matrix Permanent