Codegolf el permanente

20

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

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

ingrese la descripción de la imagen aquí

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

Como ejemplo (de la wiki):

ingrese la descripción de la imagen aquí

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.


fuente
12
¿Podría por favor eliminar el requisito complejo? Creo que arruina un desafío por lo demás agradable. Cada lenguaje que no tiene aritmética compleja incorporada ahora tiene que hacer una tarea totalmente separada.
xnor
66
Si necesitamos manejar la matriz vacía, debe agregarla como un caso de prueba. El hecho de que realmente no pueda representar la matriz 0x0 con listas hace que esto sea un poco difícil. Personalmente, simplemente eliminaría ese requisito.
Dennis
44
No tiene sentido poner algo en la caja de arena durante 3 horas. Déle 3 días y las personas tienen la oportunidad de dar su opinión.
Peter Taylor
77
1. No son solo esolangs. Bash, por ejemplo, ni siquiera puede lidiar de forma nativa con carrozas . Excluir un idioma de la competencia solo porque carece de cierto tipo numérico, incluso si puede implementar sin esfuerzo el algoritmo deseado, es ser exigente sin ninguna buena razón. 2. Todavía no estoy seguro acerca de la matriz vacía. ¿Sería [[]](tiene una fila, la matriz vacía no) o [](no tiene profundidad 2, las matrices sí) en forma de lista?
Dennis
44
1. No estoy deseando que sea imposible resolver este desafío en Bash, pero si la mayor parte del código se usa para tratar la aritmética de números complejos, deja de ser un desafío sobre los permanentes. 2. La mayoría de las respuestas actuales, si no todas, son idiomas sin un corte de tipo de matriz para la entrada [[]].
Dennis

Respuestas:

11

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 n 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
millas
fuente
1
Wow es todo lo que puedo decir.
13

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
Christian Sievers
fuente
2
¡Siempre sea bienvenido una solución de Haskell!
8

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.
Dennis
fuente
¡Es demasiado bueno!
7

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])
Feersum
fuente
6

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
Emigna
fuente
¡Una respuesta ligeramente sorprendente! ¿Podría dar alguna explicación?
@Lembik: Parece que aún podría ser más corto. Tengo una segunda solución del mismo tamaño hasta ahora.
Emigna
El manejo de matrices vacías ya no es necesario.
Dennis
8 bytes mediante el uso de mapas . Lástima que la nueva 05AB1E no es compatible con los números imaginarios (o que simplemente no saben cómo), ya que ahora tenemos una orden interna principal diagonal y esto podría haber sido 6 bytes: œ€Å\PO.
Kevin Cruijssen
5

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.

Jonathan Allan
fuente
4

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
Suever
fuente
1
Muy impresionante.
4

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
}
m-chrzan
fuente
1
reduceen realidad daña el recuento de bytes en comparación con la agregación manual:->a{m=0;a.permutation{|b|n=1;a.size.times{|i|n*=b[i][i]};m+=n};m}
ezrast
@ezrast ¡Gracias! Logró jugar golf en ese timescircuito también.
m-chrzan
3

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.

ezrast
fuente
2

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 .

millas
fuente
@alephalpha Esa es una buena idea usar las filas para identificar coeficientes, pero ¿no se rompería si las filas no fueran únicas?
millas
2

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.

Neil
fuente
@ETHproductions Nunca aprendo ...
Neil
1
Exactamente mi código, recién publicado 14 horas antes, intentaré agregar números complejos
edc65
2

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!

gggg
fuente