permanent of square matrix

[Albert Chan]

Computation of the permanent of a matrix #7151
0-based numpy npperm(M) translated to 1-based HP Prime cas code

Code:

#cas
permanent(M) :=
BEGIN
 LOCAL n,d,j,s,f,v,p;
 n := dim(M)[j:=s:=1];
 d := makelist(2,1,n);
 f := range(1,n+1);
 v := map(sum, transpose(M));
 p := product(v);
 WHILE j < n DO
  v -= d[j]*M[j]
  d[j] := -d[j]
  s := -s
  p += s*product(v);
  f[1] := 1;
  f[j] := f[j+1];
  f[j+1] := j+1;
  j := f[1];
 END;
 RETURN p/2**(n-1)
END;
#end

Code does not generate sub-matrixes, very efficient!

> m := ranm(9,9)

Code:

[[ 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]]

> permanent(m) /* time = 0.008 sec */

−3500631868051794540

Lets try naive implementation

> per(m)            /* time = 95.68 sec */

−3500631868051794540