Tantangannya adalah menulis codegolf untuk Hafnian dari sebuah matriks . The Hafnian dari 2n
-by- 2n
matriks simetris A
didefinisikan sebagai:
Di sini S 2n mewakili set semua permutasi bilangan bulat dari 1
ke2n
, yaitu [1, 2n]
.
Tautan wikipedia berbicara tentang matriks kedekatan tetapi kode Anda harus berfungsi untuk matriks masukan simetris yang bernilai nyata.
Bagi mereka yang tertarik pada aplikasi Hafnian, tautan mathoverflow membahas lebih banyak lagi.
Namun kode Anda dapat mengambil input yang diinginkan dan memberikan output dalam format apa pun yang masuk akal, tetapi harap sertakan dalam jawaban Anda contoh yang lengkap, termasuk instruksi yang jelas tentang cara memasok input ke kode Anda.
Matriks input selalu berbentuk bujur sangkar dan paling banyak 16 x 16. Tidak perlu lagi menangani matriks kosong atau matriks dimensi ganjil.
Implementasi referensi
Berikut ini beberapa contoh kode python dari 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
Halaman wiki sekarang (2 Maret 2018) telah diperbarui oleh ShreevatsaR untuk memasukkan cara berbeda dalam menghitung Hafnian. Akan sangat menarik melihat golf ini.
sumber
Jawaban:
R ,
150142127119 byteCobalah online!
Menggunakan trik yang sama saya menemukan golf jawaban ini untuk mengindeks matriks
P
, dan @Vo menyarankan pendekatan untuk menghapus sepenuhnyafor
loop untuk -6 byte!Untuk membuat test case baru, Anda bisa melakukannya
matrix(c(values,separated,by,commas,going,across,rows),nrow=2n,ncol=2n,byrow=T)
.Penjelasan: (kodenya sama; ia menggunakan
apply
bukanfor
loop tetapi logikanya identik).sumber
N
dank
ke argumen fungsi untuk mendapatkannya ke satu pernyataan, menghapus{}
dan menyimpan dua byte lainnya.Pyth , 24 byte
Coba di sini!
Versi lama, 35 byte
Coba di sini!
sumber
a[b]
cukup untuk bersaing).xÍysè<¹sès·<ysè<è
lmao? Tambang PS adalah 40 byte dan tidak berfungsi dengan baik hah, jadi jangan ragu untuk mempostingnya, tidak yakin saya bisa menyelesaikannya sebelum saya harus pulang.Stax ,
23221917 byteJalankan dan debug secara online
Representasi ascii yang sesuai dari program yang sama adalah ini.
Program ini menderita beberapa kesalahan pembulatan titik mengambang. Secara khusus, ini melaporkan
33673.5000000011
bukan33673.5
. Tapi saya pikir akurasinya dapat diterima mengingat bahwa program ini beroperasi pada nilai floating point. Ini juga sangat lambat, mengambil hampir satu menit untuk input contoh pada mesin ini.sumber
05AB1E , 21 byte
Cobalah online!
Versi lama, 32 byte
Cobalah online!
Bagaimana itu bekerja?
sumber
èsè
, hah ... haha ... aku lemah.Jelly , 19 byte
Cobalah online!
Versi alternatif, 15 byte, tantangan tanggal kiriman
Jelly akhirnya mendapat pengindeksan array n-dimensi.
Cobalah online!
Bagaimana itu bekerja
Versi 19-byte bekerja dengan cara yang sama; hanya harus mengimplementasikannya
œị
sendiri.sumber
C (gcc) ,
288285282293292272271 byteif(...)...k=0...else...,j=0...
keif(k=j=0,...)...else...
- dan melakukan pergeseran indeks.float
matriks.2*j+++1
untukj-~j++
.int
deklarasi tipe variabel dan tidak menggunakan fungsi faktorial melainkan menghitung nilai faktorial dengan menggunakan yang sudah ada untuk loop.S=S/F/(1<<n);
keS/=F*(1<<n);
.Cobalah online!
Penjelasan
Cobalah online!
Pada intinya program adalah generator permutasi berikut yang dilewati
S_n
. Semua perhitungan Hafnian hanya dibangun di atasnya - dan golf lebih lanjut.Cobalah online!
sumber
float
matriks.2*j+++1
sama denganj+j+++1
, yang sama denganj-(-j++-1)
, jadi kita dapat menggunakan bitwise melengkapi secara efisien untuk menghemat byte:j-~j++
( Coba online )R ,
8478 byteCobalah online!
Sunting: Terima kasih kepada Vlo untuk -6 byte.
Tampaknya semua orang di sini menerapkan algoritma referensi standar dengan permutasi, tetapi saya mencoba mengambil keuntungan dari pengetahuan masyarakat yang diperoleh di tantangan terkait , yang pada dasarnya adalah tugas yang sama yang ditargetkan untuk kode tercepat daripada golf.
Ternyata untuk bahasa yang bagus dalam mengiris matriks (seperti R), algoritma rekursif:
hafnian(m) = sum(m[i,j] * hafnian(m[-rows and columns at i,j])
tidak hanya lebih cepat, tetapi juga cukup golf. Berikut adalah kode yang tidak dipisahkan:sumber
If
dengan tanda kurung, -4 untuk menggunakanF
sebagai variabel diinisialisasi, -1 untuk menetapkann
dalamif
. tio.run/##XU/LCsIwELz7FcFTVtOQl1pf1/…Jelly , 29 byte
Cobalah online!
Saya pikir
;@€€Wị@/€€P€
bagian kemungkinan bisa diturunkan. Perlu kembali lagi nanti untuk memeriksa dan menambahkan penjelasan.sumber
J
) sebelum bermain golf . Pikiran jeli berpikir sama ? sumberLḶŒ!s€2ḅL‘ịFZµPS÷JḤ$P$
TIOHaskell , 136 byte
-14 byte berkat ovs.
Cobalah online!
Ugh ...
sumber
MATL ,
292422 byteCobalah online! Atau verifikasi semua kasus uji: 1 , 2 , 3 .
Bagaimana itu bekerja
sumber
Bahasa Wolfram (Mathematica) , 85 byte
Cobalah online!
sumber
Coconut ,
165145128127 byte-1 byte terima kasih kepada Tn. Xcoder
Cobalah online!
sumber
Perl 6, 86 byte
sumber