Le défi est d'écrire du codegolf pour le permanent d'une matrice .

Le permanent d'une matrice n-by- = ( ) est défini commenAai,j

S_nReprésente ici l'ensemble de toutes les permutations de [1, n].

À titre d'exemple (du wiki):

Votre code peut prendre une entrée comme il le souhaite et donner une sortie dans n'importe quel format raisonnable, mais veuillez inclure dans votre réponse un exemple complet comprenant des instructions claires sur la façon de fournir une entrée à votre code. Pour rendre le défi un peu plus intéressant, la matrice peut inclure des nombres complexes.

La matrice d'entrée est toujours carrée et sera au maximum de 6 par 6. Vous devrez également être capable de gérer la matrice vide qui a un permanent 1. Il n'est pas nécessaire de pouvoir gérer la matrice vide (cela causait trop problèmes).

Exemples

Contribution:

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

Production:

-1.7421952844303492+2.2476833142265793j

Contribution:

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

Production:

-1.972117936608412+1.6081325306004794j

Contribution:

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

Production:

-22.92354821347135-90.74278997288275j

Vous ne pouvez pas utiliser de fonctions préexistantes pour calculer le permanent.

J, 5 octets

+/ .*

J n'offre pas de builtins pour le permanent ou le déterminant mais propose plutôt une conjonction u . v yqui se développe récursivement le ylong des mineurs et calcule dyadique u . ventre les cofacteurs et la sortie de l'appel récursif sur les mineurs. Les choix de uet vpeuvent varier. Par exemple, en utilisantu =: -/ et v =: *est -/ .*qui est le déterminant. Les choix peuvent même par %/ .!où u=: %/, réduire par division et v =: !quel est le coefficient binomial. Je ne sais pas ce que signifie cette sortie, mais vous êtes libre de choisir vos verbes.

Une implémentation alternative pour 47 octets utilisant la même méthode dans ma réponse Mathematica .

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

Cela simule un polynôme avec n variables en créant un polynôme avec une variable élevée à des puissances de 2. Ceci est tenu comme une liste de coefficients et la multiplication polynomiale est effectuée en utilisant la convolution, et l'indice à 2 ⁿ contiendra le résultat.

Une autre implémentation pour 31 octets est

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

qui est une version légèrement golfée basée sur l'expansion de Laplace tirée de l'essai J sur les déterminants .

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

Haskell, 59 octets

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

Cela fait un développement semblable à Laplace le long de la première colonne, et utilise que l'ordre des lignes n'a pas d'importance. Cela fonctionne pour n'importe quel type numérique.

L'entrée est comme une liste de listes:

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

Gelée , 10 9 octets

Œ!ŒDḢ€P€S

Essayez-le en ligne!

Comment ça fonctionne

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

Semble maladroit ... devrait être battable.

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 octets

œvyvyNè}Pˆ}¯O

Essayez-le en ligne!

Explication

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

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

Implémente l'algorithme naïf qui suit aveuglément la définition.

MATL, 17 14 octets

tZyt:tY@X])!ps

Essayez-le en ligne

Explication

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

Rubis, 74 63 octets

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

Une traduction simple de la formule. Plusieurs octets enregistrés grâce à ezrast.

Explication

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

Expansion récursive de Laplace:

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

Moins golfé:

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 n'est pas officiellement publié. Sur les versions antérieures, .sumdevra être remplacé par .reduce(:+), en ajoutant 7 octets.

Mathematica, 54 octets

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

Maintenant que les matrices vides ne sont plus prises en compte, cette solution est valable. Il provient de la page MathWorld sur les permanents .

JavaScript (ES6), 82 octets

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

Fonctionne également avec la matrice vide.

Julia 0.4 , 73 octets

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

Dans les versions plus récentes de julia, vous pouvez supprimer []les compréhensions, mais vous avez besoin using Combinatoricsde la permutationsfonction. Fonctionne avec tous les types de nombres dans Julia, y compris Complex. rest un UnitRangeobjet défini comme argument de fonction par défaut, qui peut dépendre des arguments de fonction précédents.

Essayez-le en ligne!