Python 2
Meja hingga n = 64, diverifikasi optimal dengan brute force hingga n = 32:
4 4 0001
8 4 00010001
12 6 000001010011
16 8 0000010011101011
20 10 00010001011110011010
24 12 000101001000111110110111
28 14 0001011000010011101011111011
32 14 00001101000111011101101011110010
36 18 001000101001000111110011010110111000
40 20 0010101110001101101111110100011100100100
44 18 00010000011100100011110110110101011101101111
48 24 001011011001010111111001110000100110101000000110
52 26 0011010111000100111011011111001010001110100001001000
56 28 00100111111101010110001100001101100000001010100111001011
60 30 000001101101100011100101011101111110010010111100011010100010
64 32 0001100011110101111111010010011011100111000010101000001011011001
di mana 0mewakili -1. Jika ntidak habis dibagi 4 maka m = 1optimal. Dibuat menggunakan kode ini (atau variasi kecil) tetapi dengan lebih banyak uji coba untuk yang lebih tinggi n:
from random import *
seed(10)
trials=10000
def calcm(x,n):
m=1
y=x
while 1:
y=((y&1)<<(n-1))|(y>>1)
if bin(x^y).count('1')!=n/2:
return m
m+=1
def hillclimb(x,n,ns):
bestm=calcm(x,n)
while 1:
cands=[]
for pos in ns:
xx=x^(1<<pos)
m=calcm(xx,n)
if m>bestm:
bestm=m
cands=[xx]
elif cands and m==bestm:
cands+=[xx]
if not cands:
break
x=choice(cands)
return x,bestm
def approx(n):
if n<10: return brute(n)
bestm=1
bestx=0
for trial in xrange(1,trials+1):
if not trial&16383:
print bestm,bin((1<<n)|bestx)[3:]
if not trial&1:
x=randint(0,(1<<(n/2-2))-1)
x=(x<<(n/2)) | (((1<<(n/2))-1)^x)
ns=range(n/2-2)
if not trial&7:
adj=randint(1,5)
x^=((1<<adj)-1)<<randint(0,n/2-adj)
else:
x=randint(0,(1<<(n-2))-1)
ns=range(n-2)
x,m=hillclimb(x,n,ns)
if m>bestm:
bestm=m
bestx=x
return bestm,bestx
def brute(n):
bestm=1
bestx=0
for x in xrange(1<<(n-2)):
m=calcm(x,n)
if m>bestm:
bestm=m
bestx=x
return bestm,bestx
for n in xrange(4,101,4):
m,x=approx(n)
print n,m,bin((1<<n)|x)[3:]
Pendekatannya adalah pencarian acak sederhana dengan mendaki bukit, mengambil keuntungan dari pola yang terlihat kecil n. Polanya adalah bahwa untuk optimal m, paruh kedua dari baris pertama sering memiliki jarak sunting kecil dari negasi (bitwise) di babak pertama. Hasil untuk kode di atas baik untuk yang kecil ntetapi mulai memburuk tidak lama setelah brute force menjadi tidak layak; Saya akan senang melihat pendekatan yang lebih baik.
Beberapa pengamatan:
- Ketika
nganjil, m = 1optimal karena jumlah ganjil dan negatif tidak dapat menambahkan hingga nol. (Orthogonal berarti produk titik adalah nol.)
- Kapan
n = 4k + 2, m = 1optimal karena untuk itu m >= 2kita harus memiliki n/2pembalikan tanda yang tepat di antara {(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}, dan jumlah pembalikan tanda ganjil akan menyiratkan a1 = -a1.
- Produk titik dari dua baris
idan jdalam matriks sirkulant ditentukan oleh abs(i-j). Misalnya, kalau row1 . row2 = 0begitu row4 . row5 = 0. Ini karena pasangan elemen untuk produk titik sama, hanya diputar.
- Akibatnya, untuk memeriksa ortogonalitas timbal balik, kita hanya perlu memeriksa baris berturut-turut terhadap baris pertama.
- Jika kita mewakili berturut-turut sebagai string biner dengan
0di tempat -1, kita dapat memeriksa orthogonality dari dua baris dengan mengambil bitwise XOR dan membandingkan popcount dengan n/2.
- Kita dapat memperbaiki dua elemen pertama dari baris pertama secara sewenang-wenang, karena (1) Meniadakan matriks tidak mempengaruhi apakah produk titik sama dengan nol, dan (2) Kita tahu bahwa harus ada setidaknya dua elemen yang berdekatan dengan tanda yang sama dan dua elemen yang berdekatan dengan tanda yang berbeda, sehingga kita dapat memutar untuk menempatkan pasangan yang diinginkan di awal.
- Suatu solusi
(n0, m0)akan secara otomatis memberikan solusi (k * n0, m0)untuk arbitrer k > 1, dengan (berulang kali) menggabungkan baris pertama dengan dirinya sendiri. Konsekuensinya adalah bahwa kita dapat dengan mudah memperoleh m = 4untuk setiap nhabis dibagi 4.
Itu wajar untuk menduga bahwa itu n/2adalah batas atas yang ketat untuk mkapan n > 4, tetapi saya tidak tahu bagaimana itu akan terbukti.
