Die Herausforderung besteht darin, Codegolf für den Hafnianer einer Matrix zu schreiben . Der Hafnian einer 2n-by- 2nsymmetrischen Matrix Aist definiert als:

Hier repräsentiert S _2n die Menge aller Permutationen der ganzen Zahlen von 1bis 2n, das heißt [1, 2n].

Der Wikipedia-Link behandelt Adjazenzmatrizen, aber Ihr Code sollte für alle wirklich bewerteten symmetrischen Eingabematrizen funktionieren.

Für diejenigen, die an Anwendungen des Hafnian interessiert sind, werden im Mathoverflow- Link einige weitere Themen behandelt.

Ihr Code kann Eingaben annehmen, 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.

Die Eingabematrix ist immer quadratisch und wird höchstens 16 mal 16 sein. Es ist nicht erforderlich, die leere Matrix oder Matrizen mit ungerader Dimension zu verarbeiten.

Referenzimplementierung

Hier ist ein Beispiel für Python-Code von Mr. Xcoder.

from itertools import permutations
from math import factorial

def hafnian(matrix):
    my_sum = 0
    n = len(matrix) // 2
    for sigma in permutations(range(n*2)):
        prod = 1
        for j in range(n):
            prod *= matrix[sigma[2*j]][sigma[2*j+1]]
        my_sum += prod
    return my_sum / (factorial(n) * 2 ** n)


print(hafnian([[0, 4.5], [4.5, 0]]))
4.5
print(hafnian([[0, 4.7, 4.6, 4.5], [4.7, 0, 2.1, 0.4], [4.6, 2.1, 0, 1.2], [4.5, 0.4, 1.2, 0]])
16.93
print(hafnian([[1.3, 4.1, 1.2, 0.0, 0.9, 4.4], [4.1, 4.2, 2.7, 1.2, 0.4, 1.7], [1.2, 2.7, 4.9, 4.7, 4.0, 3.7], [0.0, 1.2, 4.7, 2.2, 3.3, 1.8], [0.9, 0.4, 4.0, 3.3, 0.5, 4.4], [4.4, 1.7, 3.7, 1.8, 4.4, 3.2]])
262.458

Die Wiki-Seite wurde jetzt (2. März 2018) von ShreevatsaR aktualisiert und enthält nun eine andere Methode zur Berechnung des Hafnian. Es wäre sehr interessant, dieses Golfspiel zu sehen.

R , 150 142 127 119 Bytes

function(A,N=nrow(A),k=1:(N/2)*2)sum(apply(gtools::permutations(N,N),1,function(r)prod(A[cbind(r[k-1],r[k])])))/prod(k)

Probieren Sie es online!

Benutzt den gleichen Trick, den ich entdeckt habe, als ich diese Antwort abgetastet habe , um die Matrix zu indizieren P, und @Vlo schlug einen Ansatz vor, um die forSchleife für -6 Bytes vollständig zu entfernen !

Sie können einen neuen Testfall erstellen matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T).

Erläuterung: (Der Code ist derselbe. Er verwendet applyeher eine als eine forSchleife, aber die Logik ist ansonsten identisch.)

function(A){
N <- nrow(A)                   #N = 2*n
k <- 1:(N/2) * 2               #k = c(2,4,...,N) -- aka 2*j in the formula
P <- gtools::permutations(N,N) #all N-length permutations of 1:N
for(i in 1:nrow(P))
 F <- F + prod(A[cbind(P[i,k-1],P[i,k])]) # takes the product of all A_sigma(2j-1)sigma(2j) for fixed i and adds it to F (initialized to 0)
F / prod(k)                    #return value; prod(k) == n! * 2^n
}

Pyth , 24 Bytes

sm*Fmc@@Qhkek2d{mScd2.pU

Probieren Sie es hier aus!

Alte Version, 35 Bytes

*c1**FK/lQ2^2Ksm*Fm@@Q@[email protected]

Probieren Sie es hier aus!

Stax , 23 22 19 17 Bytes

ü;Y╙◘▌Φq↓ê²╧▐å↑┌C

Führen Sie es online aus und debuggen Sie es

Dies ist die entsprechende ASCII-Darstellung desselben Programms.

%r|TF2/{xsE@i^H/m:*+

Das Programm leidet unter einem Gleitkomma-Rundungsfehler. Insbesondere berichtet es 33673.5000000011statt 33673.5. Aber ich denke, die Genauigkeit ist akzeptabel, da dieses Programm mit Gleitkommawerten arbeitet. Es ist auch sehr langsam und dauert für die Beispieleingaben auf diesem Computer fast eine Minute.

%                             get size of matrix
 r|T                          get all permutations of [0 ... size-1]
    F                         for each, execute the rest of the program
     2/                       get consecutive pairs
       {        m             map each pair... 
        xsE@                      the matrix element at that location
            i^H/                  divided by 2*(i+1) where i=iteration index
                 :*           product of array
                   +          add to running total

05AB1E , 21 Bytes

ā<œε2ô{}Ùεε`Isèsè;]PO

Probieren Sie es online!

Alte Version, 32 Bytes

āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/

Probieren Sie es online!

Wie es funktioniert?

āœvIg;©Lε·UIyX<èèyXèè}P}Oθ®!/®o/ – Full program. Argument: A matrix M.
ā                                – The range [1 ... len(M)].
 œ                               – Permutations.
  v                    }         – Iterate over the above with a variable y.
   Ig;©                          – Push len(M) / 2 and also store it in register c.
       Lε            }           – For each integer in the range [1 ... ^]:
         ·U                      – Double it and store it in a variable X.
            yX<                  – Push the element of y at index X-1.
           I   è                 – And index with the result into M.
                yXè              – Push the element of y at index X.
                   è             – And index with the result into ^^.
                      P          – Take the product of the resulting list.
                        O        – Sum the result of the mapping.
                         θ       – And take the last element*.
                          ®!     – Take the factorial of the last item in register c.
                             ®o  – Raise 2 to the power of the last item in register c.
                            /  / – And divide the sum of the mapping accordingly.

* – Yeah, this is needed because I mess up the stack when pushing so many values in the loop and not popping correctly ;P

Jelly , 19 Bytes

LŒ!s€2Ṣ€QḅL_LịFHP€S

Probieren Sie es online!

Alternative Version, 15 Byte, Herausforderung nach Datum

LŒ!s€2Ṣ€QœịHP€S

Jelly hat endlich eine n-dimensionale Array-Indizierung erhalten.

Probieren Sie es online!

Wie es funktioniert

LŒ!s€2Ṣ€QœiHP€S  Main link. Argument: M (matrix / 2D array)

L                Take the length, yielding 2n.
 Œ!              Generate all permutations of [1, ..., 2n].
   s€2           Split each permutation into pairs.
      Ṣ€         Sort the pair arrays.
        Q        Unique; deduplicate the array of pair arrays.
                 This avoids dividing by n! at the end.
           H     Halve; yield M, with all of its elements divided by 2.
                 This avoids dividing by 2**n at the end.
         œị      At-index (n-dimensional); take each pair of indices [i, j] and
                 yield M[i][j].
            P€   Take the product the results corresponding the same permutation.
              S  Take the sum of the products.

Die 19-Byte-Version funktioniert ähnlich. es muss sich nur selbst implementieren œị.

...ḅL_LịFH...    Return value: Array of arrays of index pairs. Argument: M

    L            Length; yield 2n.
   ḅ             Convert each pair of indices [i, j] from base 2n to integer,
                 yielding ((2n)i + j).
     _L          Subtract 2n, yielding ((2n)(i - 1) + j).
                 This is necessary because indexing is 1-based in Jelly, so the
                 index pair [1, 1] must map to index 1.
        F        Yield M, flattened.
       ị         Take the indices to the left and get the element at these indices
                 from the array to the right.
         H       Halve; divide all retrieved elements by 2.

C (gcc) , 288 285 282 293 292 272 271 Bytes

• Sparte drei Bytes durch Fummeln mit zwei Post-Inkrementen und für die Platzierung der Schleife.
• Sparte drei Bytes durch Fummeln mit einem anderen Nachinkrement, wobei beide Variableninitialisierungen vor dem Zweig verschoben wurden - Golfen if(...)...k=0...else...,j=0...aufif(k=j=0,...)...else... - und eine Indexverschiebung durchgeführt.
• Benötigt elf Bytes bei der Unterstützung float Matrizen.
• Sparte ein Byte dank Mr. Xcoder ; Golfen 2*j+++1zuj-~j++ .
• 20 Bytes gespart durch Entfernen eines überflüssigen int Variablentypdeklaration und Verzicht auf eine Fakultätsfunktion, sondern Berechnung des Fakultätswerts mithilfe einer bereits vorhandenen for-Schleife.
• Ein Byte durch Golfen S=S/F/(1<<n);auf gespeichert S/=F*(1<<n);.

float S,p,F;j,i;s(A,n,P,l,o,k)float*A;int*P;{if(k=j=0,o-l)for(;k<l;s(A,n,P,l,o+1))P[o]=k++;else{for(p=-l;j<l;j++)for(i=0;i<l;)p+=P[j]==P[i++];if(!p){for(F=p=1,j=0;j<n;F*=j)p*=A[P[2*j]*2*n+P[j-~j++]];S+=p;}}}float h(A,n)float*A;{int P[j=2*n];S=0;s(A,n,P,j,0);S/=F*(1<<n);}

Probieren Sie es online!

Erläuterung

float S,p,F;                    // global float variables: total sum, temporary, factorial
j,i;                            // global integer variables: indices
s(A,n,P,l,o,k)float*A;int*P;{   // recursively look at every permutation in S_n
 if(k=j=0,o-l)                  // initialize k and j, check if o != l (possible  permutation not yet fully generated)
  for(;k<l;s(A,n,P,l,o+1))      // loop through possible values for current possible  permuation position
   P[o]=k++;                    // set possible  permutation, recursively call (golfed into the for loop)
 else{for(p=-l;j<l;j++)         // there exists a possible permutation fully generated
  for(i=0;i<l;)                 // test if the possible permutation is a bijection
   p+=P[j]==P[i++];             // check for unique elements
  if(!p){                       // indeed, it is a permutation
   for(F=p=1,j=0;j<n;F*=j)      // Hafnian product loop and calculate the factorial (over and over to save bytes)
    p*=A[P[2*j]*2*n+P[j-~j++]]; // Hafnian product
   S+=p;}}}                     // add to sum
float h(A,n)float*A;{           // Hafnian function
 int P[j=2*n];S=0;              // allocate permutation memory, initialize sum
 s(A,n,P,j,0);                  // calculate Hafnian sum
 S/=F*(1<<n);}                  // calculate Hafnian

Probieren Sie es online!

Kern des Programms ist der folgende Permutationsgenerator, der durchschleift S_n. Alle hafnianischen Berechnungen bauen einfach darauf auf - und werden weiterentwickelt.

j,i,p;Sn(A,l,o,k)int*A;{          // compute every element in S_n
 if(o-l)                          // o!=l, the permutation has not fully been generated
  for(k=0;k<l;k++)                // loop through the integers [0, n)
   A[o]=k,Sn(A,l,o+1);            // modify permutation, call recursively
 else{                            // possible permutation has been generated
  for(p=-l,j=0;j<l;j++)           // look at the entire possible permutation
   for(i=0;i<l;i++)p+=A[j]==A[i]; // check that all elements appear uniquely
  if(!p)                          // no duplicat elements, it is indeed a permutation
   for(printf("["),j=0;j<l        // print
   ||printf("]\n")*0;)            //  the
    printf("%d, ",A[j++]);}}      //   permutation
main(){int l=4,A[l];Sn(A,l,0);}   // all permutations in S_4

Probieren Sie es online!

R , 84 78 Bytes

h=function(m)"if"(n<-nrow(m),{for(j in 2:n)F=F+m[1,j]*h(m[v<--c(1,j),v]);F},1)

Probieren Sie es online!

Edit: Danke an Vlo für -6 Bytes.

Es scheint, dass jeder hier den Standardreferenzalgorithmus mit Permutationen implementiert, aber ich habe versucht, das Community-Wissen zu nutzen, das bei der damit verbundenen Herausforderung gewonnen wurde. Diese Aufgabe zielt im Grunde auf den schnellsten Code ab, anstatt auf Golf.

Es stellt sich heraus, dass der rekursive Algorithmus für eine Sprache, die sich gut zum Schneiden von Matrizen (wie R) hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])eignet, nicht nur schneller ist, sondern auch ziemlich golfen kann. Hier ist der ungolfed Code:

hafnian<-function(m)
{
    n=nrow(m)
    #Exits one step earlier than golfed version
    if(n == 2) return(m[1,2])
    h = 0
    for(j in 2:n) {
        if(m[1,j] == 0) next
        h = h + m[1,j] * hafnian(m[c(-1,-j),c(-1,-j)])
    }
    h
}

Gelee , 29 Bytes

LHµ2*×!
LŒ!s€2;@€€Wị@/€€P€S÷Ç

Probieren Sie es online!

Ich denke, das ;@€€Wị@/€€P€Teil kann wahrscheinlich abgespielt werden. Müssen später zurückkommen, um zu überprüfen und eine Erklärung hinzuzufügen.

Haskell , 136 Bytes

-14 bytes dank ovs.

import Data.List
f m|n<-length m`div`2=sum[product[m!!(s!!(2*j-2)-1)!!(s!!(2*j-1)-1)/realToFrac(2*j)|j<-[1..n]]|s<-permutations[1..n*2]]

Probieren Sie es online!

Pfui...

MATL , 29 24 22 Bytes

Zy:Y@!"G@2eZ{)tn:E/pvs

Probieren Sie es online! Oder überprüfen Sie alle Testfälle: 1 , 2 , 3 .

Wie es funktioniert

Zy       % Size of (implicit) input: pushes [2*n 2*n], where the
         % input is a 2*n × 2*n matrix. 
:        % Range: gives row vector [1 2 ... 2*n]
Y@       % All permutation of that vector as rows of a matrix
!"       % For each permutation 
  G      %   Push input matrix
  @      %   Push current permutation
  2e     %   Reshape as a 2-row array
  Z{     %   Split rows into a cell array of size 2
  )      %   Reference indexing. With a cell array as index this
         %   applies element-wise indexing (similar to sub2ind).
         %   Gives a row vector with the n matrix entries selected
         %   by the current permutation
  t      %   Duplicate
  n:     %   Number of elements, range: this gives [1 2 ... n]
  E      %   Double, element-wise: gives [2 4 ... 2*n]
  /      %   Divide, element-wise
  p      %   Product
  vs     %   Vertically concatenate and sum
         % End (implicit). Display (implicit)

Wolfram Language (Mathematica) , 85 Byte

#[[s[[j]],s[[n+j]]]]~Product~{j,n}~Sum~{s,n=Tr[1^#]/2;Permutations@Range[2n]}/n!/2^n&

Probieren Sie es online!

Kokosnuss , 165 145 128 127 Bytes

-1 Byte danke an Herrn Xcoder

m->sum(reduce((o,j)->o*m[p[2*j]][p[j-~j]]/-~j/2,range(len(m)//2),1)for p in permutations(range(len(m))))
from itertools import*

Probieren Sie es online!

Perl 6, 86 Bytes

{my \n=$^m/2;^$m .permutations.map({[*] .map(->\a,\b{$m[a][b]})}).sum/(2**n*[*] 1..n)}