Po pierwsze, niektóre definicje.

Hadamarda macierz jest macierzą kwadratową, których pozycje są albo +1 lub -1, a których rzędy są wzajemnie ortogonalne. Hadamarda przypuszczenie proponuje utworzenie macierzy Hadamarda porządku 4k istnieje dla każdej dodatniej liczby całkowitej K.

Circulant matryca jest szczególny rodzaj osnowy, gdzie każdy wektor rząd jest obracany element do prawej względem rzędu poprzedniego wektora. Oznacza to, że macierz jest zdefiniowana przez jej pierwszy wiersz.

Jest znane , że z wyjątkiem 4 przez cztery matryce, istnieją żadne circulant macierzy Hadamarda .

Macierz o m rzędach i n> = m kolumnach jest częściowo krążąca , jeśli jest to pierwsze m wierszy jakiejś matrycy krążącej.

Zadanie

Dla każdej parzystej liczby całkowitej n rozpoczynającej się od 2, wypisz wielkość największej częściowej macierzy krążącej z wpisami + -1 i n kolumn, które mają właściwość polegającą na tym, że wszystkie jej rzędy są wzajemnie ortogonalne.

Wynik

Twój wynik jest najwyższy, ntak że dla wszystkich k <= nnikt inny nie opublikował lepszej poprawnej odpowiedzi niż ty. Oczywiście, jeśli masz wszystkie optymalne odpowiedzi, otrzymasz wynik za najwyższą, nktórą opublikujesz. Jednak nawet jeśli twoja odpowiedź nie jest optymalna, nadal możesz uzyskać wynik, jeśli nikt inny go nie pokona.

Języki i biblioteki

Możesz użyć dowolnego dostępnego języka i bibliotek, które ci się podobają. Tam, gdzie jest to wykonalne, dobrze byłoby móc uruchomić kod, więc proszę podać pełne wyjaśnienie, jak uruchomić / skompilować kod w systemie Linux, jeśli to w ogóle możliwe.

Wiodące wpisy

• 64 autorstwa Mitcha Schwartza w Pythonie

Python 2

Tabela do n = 64, zweryfikowana optymalna z brutalną siłą do 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

gdzie 0reprezentuje -1. Jeśli nnie jest podzielna przez 4, m = 1jest optymalna. Wygenerowano przy użyciu tego kodu (lub jego niewielkich odmian), ale z większą liczbą prób dla wyższych 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:]

Podejście jest prostym, losowym wyszukiwaniem ze wspinaniem się na wzgórze, wykorzystując wzór zauważony dla małych n. Wzór jest taki, że dla optymalnego m, druga połowa pierwszego rzędu często ma małą odległość edycji od (bitowej) negacji pierwszej połowy. Wyniki powyższego kodu są dobre dla małych, nale zaczynają się pogarszać niedługo po tym, jak brutalna siła stanie się niewykonalna; Byłbym szczęśliwy widząc lepsze podejście.

Niektóre spostrzeżenia:

• Kiedy njest nieparzyste, m = 1jest optymalne, ponieważ nieparzysta liczba jednych i ujemnych nie może zsumować się do zera. (Ortogonalny oznacza, że ​​iloczyn skalarny wynosi zero.)
• Kiedy n = 4k + 2, m = 1jest optymalny, ponieważ w celu m >= 2musimy mieć dokładnie n/2podpisać między odwrócenia {(a1,a2), (a2,a3), ... (a{n-1},an), (an,a1)}, a nieparzysta liczba odwrócenia znak oznaczałby a1 = -a1.
• Iloczyn skalarny dwóch rzędach ii jw circulant matrycy zależy od abs(i-j). Na przykład, jeśli row1 . row2 = 0wtedy row4 . row5 = 0. Jest tak, ponieważ pary elementów dla iloczynu kropkowego są takie same, tylko obrócone.
• W związku z tym do sprawdzania wzajemnej ortogonalności musimy jedynie sprawdzać kolejne wiersze względem pierwszego wiersza.
• Jeśli reprezentujemy wiersz jako ciąg binarny 0zamiast -1, możemy sprawdzić ortogonalność dwóch wierszy, biorąc bitowe xor i porównując liczbę popcount n/2.
• Możemy naprawić dowolnie dwa pierwsze elementy pierwszego rzędu, ponieważ (1) Negacja macierzy nie wpływa na to, czy iloczyn kropek jest równy zero, i (2) Wiemy, że muszą istnieć co najmniej dwa sąsiednie elementy o tym samym znaku i dwa sąsiednie elementy o różnym znaku, dzięki czemu możemy obracać, aby umieścić żądaną parę na początku.
• Rozwiązanie (n0, m0)automatycznie poda rozwiązania (k * n0, m0)arbitralne k > 1, poprzez (wielokrotne) połączenie pierwszego rzędu z samym sobą. Konsekwencją jest to, że możemy łatwo uzyskać m = 4dla każdego npodzielnego przez 4.

Naturalne jest przypuszczenie, że n/2jest to górna granica, mkiedy n > 4, ale nie wiem, jak to można udowodnić.