Codegolf the Hafnian

22

Wyzwanie polega na napisaniu kodegolfa dla Hafniana matrycy . Hafnian o 2n-by- 2nmatrycy symetrycznym Ajest zdefiniowany jako:

wprowadź opis zdjęcia tutaj

Tutaj S 2n reprezentuje zestaw wszystkich permutacji liczb całkowitych od 1do 2n, to znaczy [1, 2n].

Link do wikipedii mówi o macierzach przylegania, ale twój kod powinien działać dla wszystkich symetrycznych macierzy wejściowych o wartościach rzeczywistych.

Dla zainteresowanych aplikacjami Hafnian link do mathoverflow omawia więcej.

Kod może przyjmować dane wejściowe w dowolny sposób i dawać dane wyjściowe w dowolnym rozsądnym formacie, ale w odpowiedzi należy podać pełny sprawdzony przykład, w tym jasne instrukcje dotyczące sposobu wprowadzania danych wejściowych do kodu.

Matryca wejściowa jest zawsze kwadratowa i będzie miała maksymalnie 16 na 16. Nie ma potrzeby obsługi pustej macierzy lub macierzy o nieparzystym wymiarze.

Realizacja referencyjna

Oto przykładowy kod python od pana Xcodera.

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

Strona wiki została teraz (2 marca 2018 r.) Zaktualizowana przez ShreevatsaR, aby zawierała inny sposób obliczania Hafniana. Byłoby bardzo interesujące zobaczyć ten golf.

użytkownik202729
źródło
5
Myślę, że łatwiej byłoby to przetrawić dzięki nieformalnemu wyjaśnieniu hafniana. Coś w rodzaju: weź wszystkie podzbiory n pozycji macierzy, gdzie ich n indeksów wierszy i n indeksów kolumn tworzy partycję 1..2n, weź iloczyn każdego z nich, dodaj je i skaluj sumę.
xnor

Odpowiedzi:

9

R , 150 142 127 119 bajtów

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)

Wypróbuj online!

Używa tej samej sztuczki, którą odkryłem, grając w golfa w dół tej odpowiedzi, aby zindeksować macierz P, a @ Vlo zasugerował podejście do całkowitego usunięcia forpętli dla -6 bajtów!

Aby utworzyć nowy przypadek testowy, możesz to zrobić matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T).

Objaśnienie: (kod jest taki sam; używa applyraczej forpętli niż pętli, ale logika jest w przeciwnym razie identyczna).

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
}

Giuseppe
źródło
Apply jest tańszy o 2 bajty, co pozwala na dodatkowe 4 bajty oszczędności poprzez zaciśnięcie razem innych linii. tio.run/##PY6xDoIwEIZ3nsLxzpxiS4ymkYEXYHIjDFDEEKBtSokS47PX4sDw5/... Jest również dość interesujące, że podstawa R nie ma funkcji permutacji dla statystycznego języka programowania
Vlo
@ Vlo bardzo miło! możemy przenosić argumenty funkcji Ni przenosić kje do jednej instrukcji, usuwając {}i zapisując kolejne dwa bajty.
Giuseppe
@Giuseppe Darn ciągle zapomina, że ​​można je zdefiniować w args funkcji. Spędziłem kilka minut, próbując
wypalić
8

Pyth , 24 bajty

sm*Fmc@@Qhkek2d{mScd2.pU

Wypróbuj tutaj!


Stara wersja, 35 bajtów

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

Wypróbuj tutaj!

Pan Xcoder
źródło
3
Obecnie prowadzi, ale musisz się obawiać, że odpowiedzi Jelly się pojawią .... :)
Eh Jelly na pewno pobije mnie o około 10 bajtów. Pyth nie jest najlepszym narzędziem do pracy
Mr. Xcoder
05AB1E wygląda na to, że może nawet wiązać Pytha (wierzcie lub nie, wreszcie wyzwanie matrycowe, w którym a[b]wystarczy konkurować).
Magic Octopus Urn
@MagicOctopusUrn Mam już rozwiązanie 05AB1E, które pokonuje Pytha :-) Nie zamierzam tego publikować (przynajmniej na razie)
Mr. Xcoder
Czy to coś w stylu xÍysè<¹sès·<ysè<èLmao? PS Mine ma 40 bajtów i nie działa tak dobrze hah, więc nie krępuj się opublikować, nie jestem pewien, czy uda mi się skończyć, zanim będę musiał wrócić do domu.
Magic Octopus Urn
6

Stax , 23 22 19 17 bajtów

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

Uruchom i debuguj online

Odpowiada to reprezentacji ascii tego samego programu.

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

W programie występuje błąd zaokrąglania zmiennoprzecinkowego. W szczególności raportuje 33673.5000000011zamiast 33673.5. Myślę jednak, że dokładność jest do przyjęcia, biorąc pod uwagę, że program ten działa na wartościach zmiennoprzecinkowych. Jest również bardzo wolny, zajmuje prawie minutę na przykładowe dane wejściowe na tym komputerze.

%                             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
rekurencyjny
źródło
1
Bardzo imponujące!
5

05AB1E , 21 bajtów

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

Wypróbuj online!


Stara wersja, 32 bajty

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

Wypróbuj online!

Jak to działa?

āœ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
Pan Xcoder
źródło
1
Bez żartów èsè, hah ... haha ​​... Jestem karna.
Magic Octopus Urn
@MagicOctopusUrn Naprawiono ... Zapomniałem, że 05AB1E ma 0 indeksów> _ <
Mr. Xcoder
3

Galaretka , 19 bajtów

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

Wypróbuj online!

Alternatywna wersja, 15 bajtów, wyzwanie postdate

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

Galaretka wreszcie uzyskała indeksowanie macierzy n-wymiarowych.

Wypróbuj online!

Jak to działa

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.

Wersja 19-bajtowa działa w podobny sposób; po prostu musi się wprowadzić œị.

...ḅ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.
Dennis
źródło
3

C (gcc) , 288 285 282 293 292 272 271 bajtów

  • Zaoszczędzono trzy bajty, bawiąc się dwoma przyrostami i umieszczając pętle.
  • Zapisane przez trzy bajty błahy z anothter post-przyrostu, przenosząc obie zmienne inicjacji Zanim oddział - golfed if(...)...k=0...else...,j=0...doif(k=j=0,...)...else... - i wykonano przesunięcie indeksu.
  • Wymagane jedenaście bajtów przez obsługę float macierzy.
  • Zapisano bajt dzięki Mr. Xcoder ; grać 2*j+++1w golfaj-~j++ .
  • Zaoszczędzono dwadzieścia bajtów, usuwając zbędne int deklarację typu zmiennej i nie używając funkcji silni, lecz zamiast tego obliczając wartość silni przy użyciu już istniejącej pętli for.
  • Zapisano bajt, grając S=S/F/(1<<n);w golfa 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);}

Wypróbuj online!

Wyjaśnienie

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

Wypróbuj online!

Rdzeniem programu jest następujący generator permutacji, który przechodzi przez pętlę S_n. Całe obliczenia Hafniana są po prostu oparte na nim - i dalej w golfa.

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

Wypróbuj online!

Jonathan Frech
źródło
1
Wspaniale jest mieć odpowiedź w języku C, ale jak sugerujesz, obecnie nie jest ona zgodna.
@Lembik Naprawiono. Teraz obsługuje floatmacierze.
Jonathan Frech,
2*j+++1jest równoważne z j+j+++1, co jest tym samym co j-(-j++-1), więc możemy efektywnie wykorzystać bitowe uzupełnienie, aby zapisać bajt: j-~j++( Wypróbuj online )
Pan Xcoder
3

R , 84 78 bajtów

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)

Wypróbuj online!

Edycja: Dzięki Vlo za -6 bajtów.

Wygląda na to, że wszyscy tutaj wdrażają standardowy algorytm referencyjny z permutacjami, ale starałem się wykorzystać wiedzę społeczności zdobytą w powiązanym wyzwaniu , które jest w zasadzie tym samym zadaniem ukierunkowanym na najszybszy kod zamiast golfa.

Okazuje się, że dla języka, który jest dobry w krojeniu macierzy (jak R), algorytm rekurencyjny: hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])jest nie tylko szybszy, ale także dość golfowy. Oto nielepszy kod:

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
}
Kirill L.
źródło
Bardzo miła odpowiedź. -1 do wywołania Ifz nawiasami, -4 do użycia Fjako zmienna zainicjowana, -1 do przypisania nw obrębie if. tio.run/##XU/LCsIwELz7FcFTVtOQl1pf1/…
Vlo
schludny! Powiedziałbym, że opublikuj to w wyzwaniu prędkości, ale prawdopodobnie istnieje kilka innych optymalizacji (takich jak gwintowanie), które można wprowadzić, i chociaż R nie jest dokładnie znany ze swojej prędkości, dobrze byłoby mieć go tam w celach informacyjnych .
Giuseppe
Zrób to do celów porównawczych!
Vlo
Właściwie próbowałem przetestować to pod kątem szybkości, ale szybko zniechęciły mnie wyniki. Najwolniejsze przesyłanie Pythona w wyzwaniu prędkości przy użyciu tego samego dokładnego algorytmu blokuje matrycę 24x24 w ciągu kilku sekund na TIO, ale R. Na mojej lokalnej maszynie również nie zareagował w rozsądnym czasie, nawet jeśli wspomagano go zapamiętywaniem z paczki „memo” ...
Kirill L.
2

Galaretka , 29 bajtów

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

Wypróbuj online!

Myślę, że ;@€€Wị@/€€P€część można prawdopodobnie zagrać w golfa. Musisz wrócić później, aby sprawdzić i dodać wyjaśnienie.

dylnan
źródło
Identyczne z moim rozwiązaniem (z wyjątkiem J) przed rozpoczęciem gry w golfa . Galaretowe umysły myślą podobnie ? źródło
user202729,
Byłem w stanie to nieco zmniejszyć, refaktoryzując część, o której wspomniałeś, a także podział na 2 i silnię. LḶŒ!s€2ḅL‘ịFZµPS÷JḤ$P$ TIO
mile
@ user202729 haha ​​nice
dylnan
@miles Wow, to dużo oszczędności.
Zredaguję
2

Haskell , 136 bajtów

-14 bajtów dzięki 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]]

Wypróbuj online!

Ugh ...

całkowicie ludzki
źródło
2

MATL , 29 24 22 bajtów

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

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe: 1 , 2 , 3 .

Jak to działa

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)
Luis Mendo
źródło
1

Kokos , 165 145 128 127 127 bajtów

-1 bajt dzięki Mr. 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*

Wypróbuj online!

ovs
źródło
1

Perl 6, 86 bajtów

{my \n=$^m/2;^$m .permutations.map({[*] .map(->\a,\b{$m[a][b]})}).sum/(2**n*[*] 1..n)}
bb94
źródło