permanent of square matrix

[Albert Chan]

(01-07-2024 07:47 PM)John Keith Wrote:  That is fantastic! Much faster than any other method that I have seen.
Even better, it turns out that we can eliminate the arrays d and f entirely, making the program shorter and a bit faster.

Translated to Lua. Yes, code very compact!

Code:

function permanent(M)
    local p,n,v = 1,#M,{}
    if n==1 then return M[1][1] end
    for i = 1,n do 
        local t = 0
        for j = 1,n do t = t+M[j][i] end
        v[i], p = t, p*t
    end
    local terms = 2^(n-1)
    for k = 1,terms-1 do
        local j, t = bit.ffs(k), 1
        local d = bit.test(k,j) and -2 or 2
        for i = 1,n do v[i] = v[i]-d*M[j][i]; t = t*v[i] end
        p = t - p
    end
    return -p/terms
end

bit.ffs(x) internally call gcc __builtin_ffs(x)

int __builtin_ffs (int x) Wrote:Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

Test with OP 9×9 random numbers

lua> m = {
:      { 86, -97, -82, 7, -27, 26, -89, 63, -49},
:      {-86, -64, -30, 70, 22, 42, 56, -9, -13},
:      { 46, 24, 49, -6, 0, 81, 18, -49, -33},
:      {-70, 8, 63, -64, 2, 62, -37, -80, -23},
:      { 65, -85, 28, -44, -22, 93, 91, 31, -21},
:      { 88, 76, -66, 66, 5, -23, 79, -88, 9},
:      { 6, -69, -8, 31, 89, 2, 97, -92, 80},
:      {-24, -17, 41, 64, -49, 0, 89, 18, -51},
:      {-42, -65, 22, -94, 76, -10, 16, -63, 39}}
lua>
lua> permanent(m) /* time = 0.00019 s */
-3500631868051796000