El desafío es escribir codegolf para el permanente de una matriz .

El permanente de una matriz n-by- = ( ) se define comonAai,j

Aquí S_nrepresenta el conjunto de todas las permutaciones de [1, n].

Como ejemplo (de la wiki):

Su código puede recibir información como lo desee y proporcionar resultados en cualquier formato razonable, pero incluya en su respuesta un ejemplo completo que incluya instrucciones claras sobre cómo proporcionar información a su código. Para hacer el desafío un poco más interesante, la matriz puede incluir números complejos.

La matriz de entrada siempre es cuadrada y será como máximo de 6 por 6. También deberá poder manejar la matriz vacía que tiene permanente 1. No es necesario poder manejar la matriz vacía (estaba causando demasiados problemas).

Ejemplos

Entrada:

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

Salida:

-1.7421952844303492+2.2476833142265793j

Entrada:

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

Salida:

-1.972117936608412+1.6081325306004794j

Entrada:

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

Salida:

-22.92354821347135-90.74278997288275j

No puede utilizar ninguna función preexistente para calcular el permanente.

J, 5 bytes

+/ .*

J no ofrece incorporaciones para lo permanente o determinante, sino que ofrece una conjunción u . v yque se expande recursivamente a lo ylargo de los menores y calcula diádica u . ventre los cofactores y la salida de la llamada recursiva a los menores. Las opciones de uy vpueden variar. Por ejemplo, usar u =: -/y v =: *es -/ .*cuál es el determinante. Las opciones pueden incluso por %/ .!dónde u=: %/, reducir por división, y v =: !cuál es el coeficiente binomial. No estoy seguro de lo que significa esa salida, pero eres libre de elegir tus verbos.

Una implementación alternativa para 47 bytes usando el mismo método en mi respuesta de Mathematica .

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

Esto simula un polinomio con n variables creando un polinomio con una variable elevada a potencias de 2. Esto se mantiene como una lista de coeficientes y la multiplicación polinomial se realiza usando convolución, y el índice en 2 ⁿ contendrá el resultado.

Otra implementación para 31 bytes es

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

que es una versión ligeramente golfizada basada en la expansión de Laplace tomada del ensayo J sobre determinantes .

Uso

   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

Haskell, 59 bytes

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

Esto hace un desarrollo similar a Laplace a lo largo de la primera columna, y usa que el orden de las filas no importa. Funciona para cualquier tipo numérico.

La entrada es como una lista de listas:

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

Jalea , 10 9 bytes

Œ!ŒDḢ€P€S

Pruébalo en línea!

Cómo funciona

Œ!Œ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.

Python 2, 75 bytes

Parece torpe ... debería ser vencible.

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

œvyvyNè}Pˆ}¯O

Pruébalo en línea!

Explicación

œ              # 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

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

Implementa el algoritmo ingenuo que sigue ciegamente la definición.

MATL, 17 14 bytes

tZyt:tY@X])!ps

Pruébalo en línea

Explicación

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

Rubí, 74 63 bytes

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

Una traducción directa de la fórmula. Varios bytes guardados gracias a ezrast.

Explicación

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

Ruby 2.4.0, 59 61 bytes

Expansión recursiva de Laplace:

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

Menos golfizado:

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 no se lanza oficialmente. En versiones anteriores, .sumdeberá ser reemplazado por .reduce(:+), agregando 7 bytes.

Mathematica, 54 bytes

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

Ahora que las matrices vacías ya no se consideran, esta solución es válida. Se origina en la página MathWorld sobre permanentes .

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

También funciona con la matriz vacía, por supuesto.

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

En las versiones más recientes de julia, puede omitir []las comprensiones, pero necesita using Combinatoricsla permutationsfunción. Funciona con todos los tipos de números en Julia, incluidos Complex. res un UnitRangeobjeto definido como un argumento de función predeterminado, que puede depender de argumentos de función anteriores.

Pruébalo en línea!