Codegolf the permanent

Question

The challenge is to write codegolf for the permanent of a matrix.

The permanent of an \$n\times n\$ matrix \$A = a_{i,j}\$) is defined as

$$\text{perm}(A) = \sum_{\sigma \in S_n} \prod^n_{i=1} a_{i,\sigma(i)}$$

Here \$S_n\$ represents the set of all permutations of \$[1, n]\$.

As an example (from the wiki):

$$\text{perm} \left( \begin{matrix} a & b & c \\ d & e & f \\ g & h & i \\ \end{matrix} \right) = aei + bfg + cdh + ceg + bdi + afh$$

Your code can take input however it wishes and give output in any sensible format but please include in your answer a full worked example including clear instructions for how to supply input to your code. To make the challenge a little more interesting, the matrix may include complex numbers.

The input matrix is always square and will be at most 6 by 6. You will also need to be able to handle the empty matrix which has permanent 1. There is no need to be able to handle the empty matrix (it was causing too many problems).

Examples

Input:

[[ 0.36697048+0.02459455j,  0.81148991+0.75269667j,  0.62568185+0.95950937j],
 [ 0.67985923+0.11419187j,  0.50131790+0.13067928j,  0.10330161+0.83532727j],
 [ 0.71085747+0.86199765j,  0.68902048+0.50886302j,  0.52729463+0.5974208j ]]

Output:

-1.7421952844303492+2.2476833142265793j

Input:

[[ 0.83702504+0.05801749j,  0.03912260+0.25027115j,  0.95507961+0.59109069j],
 [ 0.07330546+0.8569899j ,  0.47845015+0.45077079j,  0.80317410+0.5820795j ],
 [ 0.38306447+0.76444045j,  0.54067092+0.90206306j,  0.40001631+0.43832931j]]

Output:

-1.972117936608412+1.6081325306004794j

Input:

 [[ 0.61164611+0.42958732j,  0.69306292+0.94856925j,
     0.43860930+0.04104116j,  0.92232338+0.32857505j,
     0.40964318+0.59225476j,  0.69109847+0.32620144j],
   [ 0.57851263+0.69458731j,  0.21746623+0.38778693j,
     0.83334638+0.25805241j,  0.64855830+0.36137045j,
     0.65890840+0.06557287j,  0.25411493+0.37812483j],
   [ 0.11114704+0.44631335j,  0.32068031+0.52023283j,
     0.43360984+0.87037973j,  0.42752697+0.75343656j,
     0.23848512+0.96334466j,  0.28165516+0.13257001j],
   [ 0.66386467+0.21002292j,  0.11781236+0.00967473j,
     0.75491373+0.44880959j,  0.66749636+0.90076845j,
     0.00939420+0.06484633j,  0.21316223+0.4538433j ],
   [ 0.40175631+0.89340763j,  0.26849809+0.82500173j,
     0.84124107+0.23030393j,  0.62689175+0.61870543j,
     0.92430209+0.11914288j,  0.90655023+0.63096257j],
   [ 0.85830178+0.16441943j,  0.91144755+0.49943801j,
     0.51010550+0.60590678j,  0.51439995+0.37354955j,
     0.79986742+0.87723514j,  0.43231194+0.54571625j]]

Output:

-22.92354821347135-90.74278997288275j

You may not use any pre-existing functions to compute the permanent.

Answer 1

J, 5 bytes

+/ .*

J does not offer builtins for the permanent or determinant but instead offers a conjunction u . v y which recursively expands y along the minors and calculates dyadic u . v between the cofactors and the output of the recursive call on the minors. The choices of u and v can vary. For example, using u =: -/ and v =: * is -/ .* which is the determinant. Choices can even by %/ .! where u=: %/, reduce by division, and v =: ! which is binomial coefficient. I'm not sure what that output signifies but you're free to choose your verbs.

An alternative implementation for 47 bytes using the same method in my Mathematica answer.

_1{[:($@]$[:+//.*/)/0,.;@(<@(,0#~<:)"+2^i.@#)"{

This simulates a polynomial with n variables by creating a polynomial with one variable raised to powers of 2. This is held as a coefficient list and polynomial multiplication is performed using convolution, and the index at 2ⁿ will contain the result.

Another implementation for 31 bytes is

+/@({.*1$:\.|:@}.)`(0{,)@.(1=#)

which is a slightly golfed version based on Laplace expansion taken from the J essay on determinants.

Usage

   f =: +/ .*
   f 0 0 $ 0 NB. the empty matrix, create a shape with dimensions 0 x 0
1
   f 0.36697048j0.02459455 0.81148991j0.75269667 0.62568185j0.95950937 , 0.67985923j0.11419187  0.50131790j0.13067928 0.10330161j0.83532727 ,: 0.71085747j0.86199765 0.68902048j0.50886302 0.52729463j0.5974208
_1.7422j2.24768
   f 0.83702504j0.05801749 0.03912260j0.25027115 0.95507961j0.59109069 , 0.07330546j0.8569899 0.47845015j0.45077079 0.80317410j0.5820795 ,: 0.38306447j0.76444045 0.54067092j0.90206306 0.40001631j0.43832931
_1.97212j1.60813
   f 0.61164611j0.42958732 0.69306292j0.94856925 0.4386093j0.04104116 0.92232338j0.32857505 0.40964318j0.59225476 0.69109847j0.32620144 , 0.57851263j0.69458731 0.21746623j0.38778693 0.83334638j0.25805241 0.6485583j0.36137045 0.6589084j0.06557287 0.25411493j0.37812483 , 0.11114704j0.44631335 0.32068031j0.52023283 0.43360984j0.87037973 0.42752697j0.75343656 0.23848512j0.96334466 0.28165516j0.13257001 , 0.66386467j0.21002292 0.11781236j0.00967473 0.75491373j0.44880959 0.66749636j0.90076845 0.0093942j0.06484633 0.21316223j0.4538433 , 0.40175631j0.89340763 0.26849809j0.82500173 0.84124107j0.23030393 0.62689175j0.61870543 0.92430209j0.11914288 0.90655023j0.63096257 ,: 0.85830178j0.16441943 0.91144755j0.49943801 0.5101055j0.60590678 0.51439995j0.37354955 0.79986742j0.87723514 0.43231194j0.54571625
_22.9235j_90.7428

Answer 2

Haskell, 59 bytes

a#((b:c):r)=b*p(a++map tail r)+(c:a)#r
_#_=0
p[]=1
p l=[]#l

This does a Laplace-like development along the first column, and uses that the order of the rows doesn't matter. It works for any numeric type.

Input is as list of lists:

Prelude> p [[1,2],[3,4]]
10

Answer 3

Jelly, 10 9 bytes

Œ!ŒDḢ€P€S

Try it online!

How it works

Œ!ŒDḢ€P€S  Main link. Argument: M (matrix / 2D array)

Œ!         Generate all permutations of M's rows.
  ŒD       Compute the permutations' diagonals, starting with the main diagonal.
    Ḣ€     Head each; extract the main diagonal of each permutation.
      P€   Product each; compute the products of the main diagonals.
        S  Compute the sum of the products.

Answer 4

Python 2, 75 bytes

Seems clunky... should be beatable.

P=lambda m,i=0:sum([r[i]*P(m[:j]+m[j+1:],i+1)for j,r in enumerate(m)]or[1])

Answer 5

05AB1E, 19 14 13 bytes

œvyvyNè}Pˆ}¯O

Try it online!

Explanation

œ              # get all permutations of rows
 v        }    # for each permutation
  yv   }       # for each row in the permutation
    yNè        # get the element at index row-index
        P      # product of elements
         ˆ     # add product to global array
           ¯O  # sum the products from the global array

Answer 6

Python 2, 139 bytes

from itertools import*
def p(a):c=complex;r=range(len(a));return sum(reduce(c.__mul__,[a[j][p[j]]for j in r],c(1))for p in permutations(r))

repl.it

Implements the naïve algorithm which blindly follows the definition.

Answer 7

MATL, 1714 bytes

tZyt:tY@X])!ps

Try it Online

Explanation

t       % Implicitly grab input and duplicate
Zy      % Compute the size of the input. Yields [rows, columns]
t:      % Compute an array from [1...rows]
tY@     % Duplicate this array and compute all permutations (these are the columns)
X]      % Convert row/column to linear indices into the input matrix
)       % Index into the input matrix where each combination is a row
!p      % Take the product of each row
s       % Sum the result and implicitly display

Answer 8

Ruby, 74 63 bytes

->a{p=0;a.permutation{|b|n=1;i=-1;a.map{n*=b[i+=1][i]};p+=n};p}

A straightforward translation of the formula. Several bytes saved thanks to ezrast.

Explanation

->a{
    # Initialize the permanent to 0
    p=0
    # For each permutation of a's rows...
    a.permutation{|b|
        # ... initialize the product to 1,
        n=1
        # initialize the index to -1; we'll use this to go down the main diagonal
        # (i starts at -1 because at each step, the first thing we do is increment i),
        i=-1
        # iteratively calculate the product,
        a.map{
            n*=b[i+=1][i]
        }
        # increase p by the main diagonal's product.
        p+=n
    }
    p
}

Answer 9

Ruby 2.4.0, 59 61 bytes

Recursive Laplace expansion:

f=->a{a.pop&.map{|n|n*f[a.map{|r|r.rotate![0..-2]}]}&.sum||1}

Less golfed:

f=->a{
  # Pop a row off of a
  a.pop&.map{ |n|
    # For each element of that row, multiply by the permanent of the minor
    n * f[a.map{ |r| r.rotate![0..-2]}]
  # Add all the results together
  }&.sum ||
  # Short circuit to 1 if we got passed an empty matrix
  1
}

Ruby 2.4 is not officially released. On earlier versions, .sum will need to be replaced with .reduce(:+), adding 7 bytes.

Answer 10

Julia 0.4, 73 bytes

f(a,r=1:size(a,1))=sum([prod([a[i,p[i]] for i=r]) for p=permutations(r)])

In newer versions of julia you can drop the [] around the comprehensions, but need using Combinatorics for the permutations function. Works with all Number types in Julia, including Complex. r is a UnitRange object defined as a default function argument, which can depend on previous function arguments.

Try it online!

Answer 11

Mathematica, 54 bytes

Coefficient[Times@@(#.(v=x~Array~Length@#)),Times@@v]&

Now that the empty matrices are no longer considered, this solution is valid. It originates from the MathWorld page on permanents.

Answer 12

JavaScript (ES6), 82 bytes

f=a=>a[0]?a.reduce((t,b,i)=>t+b[0]*f(a.filter((_,j)=>i-j).map(c=>c.slice(1))),0):1

Works with the empty matrix too, of course.

Answer 13

Pari/GP, 44 bytes

p(m)=if(#m,sum(n=1,#m,m[1,n]*p(m[^1,^n])),1)

Try it online!

---

Pari/GP, 50 bytes

m->polcoef(vecprod([x^2^i|i<-[0..#m-1]]*m),2^#m-1)

Based on @miles's Mathematica answer.

According to Wolfram MatheWorld, the permanent of a matrix \$A = (a_{ij})\$ is the coefficient of \$x_1 \cdots x_n\$ in the polynomial \$\prod_{i=1}^{n}\sum_{j=1}^na_{ij}x_j\$. This is exactly what miles's answer does.

But in PARI/GP there isn't an easy way to generate an arbitrary number of new variables. So instead of a list variables \$[x_1, \dots, x_n]\$, I use the \$2^i\$'th powers of a single variable \$x\$, i.e., \$[x^1, \dots, x^{2^{n-1}}]\$, and take the coefficient of \$x^1 \cdots x^{2^{n-1}} = x^{2^n-1}\$.

Try it online!