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).



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




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




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



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

  • 14
    \$\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
    Commented Oct 20, 2016 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
    Commented Oct 20, 2016 at 15:07
  • 5
    \$\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\$ Commented Oct 20, 2016 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
    Commented Oct 20, 2016 at 16:53
  • 4
    \$\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
    Commented Oct 20, 2016 at 17:56

13 Answers 13


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.


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


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


   f =: +/ .*
   f 0 0 $ 0 NB. the empty matrix, create a shape with dimensions 0 x 0
   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
   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
   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
  • 1
    \$\begingroup\$ Wow is all I can say. \$\endgroup\$
    – user9206
    Commented Oct 20, 2016 at 18:35

Haskell, 59 bytes

a#((b:c):r)=b*p(a++map tail r)+(c:a)#r
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]]
  • 2
    \$\begingroup\$ Always welcome a Haskell solution! \$\endgroup\$
    – user9206
    Commented Oct 20, 2016 at 16:37

Jelly, 10 9 bytes


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

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

05AB1E, 19 14 13 bytes


Try it online!


œ              # 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
  • \$\begingroup\$ A slightly shockingly sized answer! Could you provide some explanation? \$\endgroup\$
    – user9206
    Commented Oct 20, 2016 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
    Commented Oct 20, 2016 at 14:16
  • \$\begingroup\$ Handling empty matrices is no longer required. \$\endgroup\$
    – Dennis
    Commented Oct 20, 2016 at 19:14
  • \$\begingroup\$ 8 bytes by using maps. Too bad the new 05AB1E doesn't support imaginary numbers (or I simply don't know how), since we now have a main diagonal builtin and this could have been 6 bytes: œ€Å\PO. \$\endgroup\$ Commented Dec 6, 2019 at 16:06

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))


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


MATL, 1714 bytes


Try it Online


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

Ruby, 74 63 bytes


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


    # Initialize the permanent to 0
    # For each permutation of a's rows...
        # ... initialize the product to 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),
        # iteratively calculate the product,
        # increase p by the main diagonal's product.
  • 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
    Commented Oct 21, 2016 at 2:15
  • \$\begingroup\$ @ezrast Thanks! Managed to golf down that times loop as well. \$\endgroup\$
    – m-chrzan
    Commented Oct 21, 2016 at 22:55

Ruby 2.4.0, 59 61 bytes

Recursive Laplace expansion:


Less golfed:

  # 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

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


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!


Mathematica, 54 bytes


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

  • \$\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
    Commented Oct 22, 2016 at 17:05

JavaScript (ES6), 82 bytes


Works with the empty matrix too, of course.

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

Pari/GP, 44 bytes


Try it online!

Pari/GP, 50 bytes


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.