19
\$\begingroup\$

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

The permanent of an n-by-n matrix A = (ai,j) is defined as

enter image description here

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

As an example (from the wiki):

enter image description here

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.

\$\endgroup\$
  • 12
    \$\begingroup\$ Could you please remove the complex requirement? I think it ruins an otherwise nice challenge. Every language that doesn't have built-in complex arithmetic now has to do a totally separate task. \$\endgroup\$ – xnor Oct 20 '16 at 14:48
  • 6
    \$\begingroup\$ If we need to handle the empty matrix, you should add it as a test case. The fact that you cannot really represent the 0x0 matrix with lists makes this a bit difficult. Personally, I'd just remove that requirement. \$\endgroup\$ – Dennis Oct 20 '16 at 15:07
  • 4
    \$\begingroup\$ There's no point putting something in the sandbox for 3 hours. Give it 3 days and people have a chance to give feedback. \$\endgroup\$ – Peter Taylor Oct 20 '16 at 16:43
  • 7
    \$\begingroup\$ 1. It's not just esolangs. Bash, e.g., can't even natively deal with floats. Excluding a language from the competition just because it lacks a certain numeric type, even if can effortlessly implement the desired algorithm, is just being picky for no good reason. 2. I'm still not sure about the empty matrix. Would it be [[]] (has one row, the empty matrix doesn't) or [] (doesn't have depth 2, matrices do) in list form? \$\endgroup\$ – Dennis Oct 20 '16 at 16:53
  • 3
    \$\begingroup\$ 1. I'm not daying that it's impossible to solve this challenge in Bash, but if the lion share of the code is used to deal with complex number arithmetic, it stops being a challenge about permanents. 2. Most if not all current answers is languages without a matrix type break for input [[]]. \$\endgroup\$ – Dennis Oct 20 '16 at 17:56

12 Answers 12

10
\$\begingroup\$

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 2n 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
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow is all I can say. \$\endgroup\$ – user9206 Oct 20 '16 at 18:35
12
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Always welcome a Haskell solution! \$\endgroup\$ – user9206 Oct 20 '16 at 16:37
6
\$\begingroup\$

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])
\$\endgroup\$
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ It's just too good! \$\endgroup\$ – user9206 Oct 20 '16 at 19:14
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ A slightly shockingly sized answer! Could you provide some explanation? \$\endgroup\$ – user9206 Oct 20 '16 at 14:15
  • \$\begingroup\$ @Lembik: Feels like it could be shorter still. I have a second solution of the same size so far. \$\endgroup\$ – Emigna Oct 20 '16 at 14:16
  • \$\begingroup\$ Handling empty matrices is no longer required. \$\endgroup\$ – Dennis Oct 20 '16 at 19:14
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Very impressive. \$\endgroup\$ – user9206 Oct 20 '16 at 16:48
3
\$\begingroup\$

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
}
\$\endgroup\$
  • 1
    \$\begingroup\$ reduce actually hurts your byte count compared to aggregating manually: ->a{m=0;a.permutation{|b|n=1;a.size.times{|i|n*=b[i][i]};m+=n};m} \$\endgroup\$ – ezrast Oct 21 '16 at 2:15
  • \$\begingroup\$ @ezrast Thanks! Managed to golf down that times loop as well. \$\endgroup\$ – m-chrzan Oct 21 '16 at 22:55
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @alephalpha That's a neat idea to use the rows to identify coefficients but wouldn't it break if the rows were not unique? \$\endgroup\$ – miles Oct 22 '16 at 17:05
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @ETHproductions I never learn... \$\endgroup\$ – Neil Oct 21 '16 at 8:22
  • 1
    \$\begingroup\$ Exactly my code, just published 14 hours before, I'll try to add complex numbers \$\endgroup\$ – edc65 Oct 21 '16 at 9:19
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy