Python 2
Tabelle bis n = 64
, verifiziert optimal mit roher Gewalt bis zu 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
wo 0
repräsentiert -1
. Wenn n
nicht durch 4 teilbar ist, m = 1
ist es optimal. Erstellt mit diesem Code (oder kleinen Variationen davon), aber mit mehr Versuchen für höhere 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:]
Der Ansatz ist eine einfache zufällige Suche mit Bergsteigen, wobei ein Muster genutzt wird, das für kleine bemerkt wird n
. Das Muster ist, dass für ein Optimum m
die zweite Hälfte der ersten Reihe oft einen kleinen Bearbeitungsabstand von der (bitweisen) Negation der ersten Hälfte hat. Die Ergebnisse für den obigen Code sind gut für kleine n
, beginnen sich jedoch nicht lange zu verschlechtern, nachdem rohe Gewalt nicht mehr durchführbar ist. Ich würde mich über einen besseren Ansatz freuen.
Einige Beobachtungen:
- Wann
n
ungerade ist, m = 1
ist optimal, da eine ungerade Anzahl von Einsen und negativen nicht zu Null addiert werden kann. (Orthogonal bedeutet, dass das Punktprodukt Null ist.)
- Wenn
n = 4k + 2
, m = 1
ist optimal , weil damit m >= 2
wir genau brauchen , um n/2
Umkehrungen unter schreiben {(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}
, und eine ungerade Anzahl von Vorzeichenumkehr bedeuten würde a1 = -a1
.
- Das Punktprodukt zweier Reihen
i
und j
in einer zirkulierenden Matrix wird bestimmt durch abs(i-j)
. Zum Beispiel wenn row1 . row2 = 0
dann row4 . row5 = 0
. Dies liegt daran, dass die Elementpaare für das Punktprodukt gleich sind und nur gedreht werden.
- Folglich müssen wir zur Überprüfung der gegenseitigen Orthogonalität nur aufeinanderfolgende Zeilen mit der ersten Zeile vergleichen.
- Wenn wir eine Zeile als Binärzeichenfolge mit
0
anstelle von darstellen -1
, können wir die Orthogonalität von zwei Zeilen überprüfen, indem wir bitweises xor nehmen und den Popcount mit vergleichen n/2
.
- Wir können die ersten beiden Elemente der ersten Zeile beliebig fixieren, da (1) das Negieren einer Matrix keinen Einfluss darauf hat, ob die Punktprodukte gleich Null sind, und (2) wir wissen, dass es mindestens zwei benachbarte Elemente mit demselben Vorzeichen und zwei geben muss benachbarte Elemente mit unterschiedlichem Vorzeichen, sodass wir uns drehen können, um das gewünschte Paar am Anfang zu platzieren.
- Eine Lösung
(n0, m0)
gibt automatisch Lösungen (k * n0, m0)
für beliebige k > 1
, indem die erste Zeile (wiederholt) mit sich selbst verkettet wird. Eine Konsequenz ist, dass wir leicht m = 4
für jede n
durch 4 teilbare erhalten können .
Es ist natürlich zu vermuten, dass dies n/2
eine enge Obergrenze für m
wann ist n > 4
, aber ich weiß nicht, wie dies bewiesen werden würde.