Die Herausforderung besteht darin, Codegolf für das Permanent einer Matrix zu schreiben .

Die Permanenz einer n-by- nMatrix A= ( ai,j) ist definiert als

Hier wird S_ndie Menge aller Permutationen von dargestellt [1, n].

Als Beispiel (aus dem Wiki):

Ihr Code kann Eingaben vornehmen, wie er möchte, und Ausgaben in jedem vernünftigen Format geben. Bitte fügen Sie Ihrer Antwort ein vollständiges Beispiel bei, das klare Anweisungen zur Eingabe Ihres Codes enthält. Um die Herausforderung ein wenig interessanter zu gestalten, kann die Matrix komplexe Zahlen enthalten.

Die Eingabematrix ist immer quadratisch und wird höchstens 6 mal 6 sein. Sie müssen auch in der Lage sein, mit der leeren Matrix mit permanenter 1 umzugehen. Es ist nicht erforderlich, mit der leeren Matrix umzugehen (sie hat zu viele verursacht) Probleme).

Beispiele

Eingang:

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

Ausgabe:

-1.7421952844303492+2.2476833142265793j

Eingang:

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

Ausgabe:

-1.972117936608412+1.6081325306004794j

Eingang:

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

Ausgabe:

-22.92354821347135-90.74278997288275j

Sie dürfen keine bereits vorhandenen Funktionen verwenden, um die bleibende Karte zu berechnen.

J, 5 Bytes

+/ .*

J bietet keine Builtins für die Permanente oder Determinante an, sondern eine Konjunktion, u . v ydie sich rekursiv yentlang der Minderjährigen ausdehnt und die dyadische Beziehung u . vzwischen den Cofaktoren und der Ausgabe des rekursiven Aufrufs an die Minderjährigen berechnet . Die Auswahlmöglichkeiten von uund vkönnen variieren. Zum Beispiel mit u =: -/und v =: *ist -/ .*das, was die Determinante ist. Entscheidungen können sogar durch %/ .!wo u=: %/, durch Division, und v =: !was ist Binomialkoeffizient zu reduzieren . Ich bin nicht sicher, was diese Ausgabe bedeutet, aber Sie können Ihre Verben frei wählen.

Eine alternative Implementierung für 47 Bytes unter Verwendung derselben Methode in meiner Mathematica- Antwort .

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

Dies simuliert ein Polynom mit n Variablen, indem ein Polynom mit einer auf Potenzen von 2 angehobenen Variablen erstellt wird. Dies wird als Koeffizientenliste gehalten, und die Polynommultiplikation wird unter Verwendung der Faltung durchgeführt, und der Index bei 2 ⁿ enthält das Ergebnis.

Eine andere Implementierung für 31 Bytes ist

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

Dies ist eine leicht golfene Version, die auf der Laplace-Erweiterung basiert, die dem J-Aufsatz über Determinanten entnommen ist .

Verwendung

   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

Dies führt eine Laplace-ähnliche Entwicklung entlang der ersten Spalte durch und verwendet, dass die Reihenfolge der Zeilen keine Rolle spielt. Es funktioniert für jeden numerischen Typ.

Die Eingabe erfolgt als Liste von Listen:

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

Gelee , 10 9 Bytes

Œ!ŒDḢ€P€S

Probieren Sie es online!

Wie es funktioniert

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

Scheint klobig ... sollte schlagbar sein.

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

Probieren Sie es online!

Erläuterung

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

Implementiert den naiven Algorithmus, der der Definition blind folgt.

MATL, 17 14 Bytes

tZyt:tY@X])!ps

Probieren Sie es online

Erläuterung

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

Rubin, 74 63 Bytes

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

Eine einfache Übersetzung der Formel. Dank ezrast werden mehrere Bytes eingespart.

Erläuterung

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

Mathematica, 54 Bytes

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

Diese Lösung ist gültig, da die leeren Matrizen nicht mehr berücksichtigt werden. Es stammt von der MathWorld-Seite zu permanenten Objekten .

Ruby 2.4.0, 59 61 Bytes

Rekursive Laplace-Erweiterung:

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

Weniger golfen:

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 ist nicht offiziell freigegeben. In früheren Versionen .summuss durch ersetzt werden .reduce(:+), wobei 7 Byte hinzugefügt werden.

JavaScript (ES6), 82 Byte

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

Funktioniert natürlich auch mit der leeren Matrix.

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 neueren julia-versionen kann man das []um die verständnisse fallen lassen, braucht aber using Combinatoricsdie permutationsfunktion. Funktioniert mit allen Nummerntypen in Julia, einschließlich Complex. rist ein UnitRangeObjekt, das als Standardfunktionsargument definiert ist und von vorherigen Funktionsargumenten abhängen kann.

Probieren Sie es online!