Odległość Hamminga pomiędzy dwa ciągi o równej długości jest numer pozycji, w którym odpowiednie symbole są różne.
Niech P
będzie dwójkowym ciągiem długości n
i T
dwójkowym ciągiem długości 2n-1
. Możemy obliczyć n
odległości Hamminga między podciągiem P
każdej n
długości T
w kolejności od lewej do prawej i umieścić je w tablicy (lub liście).
Przykład sekwencji odległości Hamminga
Niech P = 101
i T = 01100
. Sekwencja odległości Hamminga uzyskana z tej pary to 2,2,1
.
Definicja bliskości
Rozważmy teraz dwie takie sekwencje odległości Hamminga. Powiedz x = (0, 2, 2, 3, 0)
i y = (2, 1, 4, 4, 2)
jako przykłady. Mówimy to x
i y
jesteśmy, close
jeśli y <= x <= 2*y
lub jeśli x <= y <= 2*x
. Tutaj mnożenie skalarne i nierówności są uwzględniane elementarnie. To znaczy, dla dwóch sekwencji A
i B
, A <= B iff A[i] <= B[i]
dla wszystkich indeksów i
.
Zauważ, że sekwencje odległości Hamminga tworzą częściowy porządek w ten sposób ich porównywania. Innymi słowy, wiele par sekwencji nie jest ani większych, ani równych, ani mniejszych ani równych sobie. Na przykład (1,2)
i (2,1)
.
Korzystając z powyższego przykładu, (0, 2, 2, 3, 0) <= 2*(2, 1, 4, 4, 2) = (4, 2, 8, 8, 4)
ale (0, 2, 2, 3, 0)
nie jest większy niż (2, 1, 4, 4, 2)
. Również (2, 1, 4, 4, 2)
nie jest mniejszy ani równy 2*(0, 2, 2, 3, 0) = (0, 4, 4, 6, 0)
. W rezultacie x
i y
nie są blisko siebie.
Zadanie
Aby zwiększyć, n
zaczynając od n=1
, rozważ wszystkie możliwe pary ciągów binarnych P
o długości n
i T
długości 2n-1
. Istnieją 2^(n+2n-1)
takie pary, a zatem wiele sekwencji odległości Hamminga. Jednak wiele z tych sekwencji będzie identycznych. Zadanie polega na znalezieniu rozmiaru największego zestawu sekwencji odległości Hamminga, aby żadne dwie sekwencje nie były blisko siebie.
Twój kod powinien wypisywać jedną liczbę na wartość n
.
Wynik
Twój wynik jest ogólnie najwyższy, jaki n
Twój kod osiąga na moim komputerze w ciągu 5 minut (ale czytaj dalej). Czas dotyczy całkowitego czasu działania, a nie tylko tego czasu n
.
Aby uzyskać wyniki dla nieoptymalnych odpowiedzi, ponieważ znalezienie optymalnych odpowiedzi może być trudne, potrzebujemy nieco subtelnego systemu punktacji. Twój wynik jest najwyższą wartością, n
dla której nikt inny nie opublikował wyższej poprawnej odpowiedzi dla dowolnego rozmiaru, który jest mniejszy niż równy. Na przykład, jeśli wyprowadzasz dane wyjściowe, 2, 4, 21
a ktoś inny wyświetla dane wyjściowe, 2, 5, 15
uzyskasz wynik tylko wtedy, 1
gdy ktoś inny ma lepszą odpowiedź n = 2
. Jeśli wypiszesz wynik, 2, 5, 21
uzyskasz wynik 3
bez względu na to, co ktoś wypisze, ponieważ wszystkie te odpowiedzi są optymalne. Oczywiście, jeśli masz wszystkie optymalne odpowiedzi, otrzymasz wynik za najwyższą, n
którą opublikujesz. Jednak nawet jeśli twoja odpowiedź nie jest optymalna, nadal możesz uzyskać wynik, jeśli nikt inny go nie pokona.
Przykładowe odpowiedzi i działający przykład
(Te odpowiedzi są jeszcze niezaznaczone. Niezależna weryfikacja byłaby wdzięczna).
Dzięki ETHproductions:
- n = 1 daje 2.
- n = 2 daje 5.
- n = 3 daje 21.
Spójrzmy n = 2
bardziej szczegółowo. W tym przypadku pełna lista sekwencji odległości Hamminga (reprezentowana tutaj przez krotki) to:
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
Widzimy, że (0,0)
nie jest to zbliżone do żadnej innej krotki. W rzeczywistości, jeśli weźmiemy (0, 0)
, (0, 1)
, (1, 0)
, (2, 1)
, (1,2)
to żaden z tych krotek są zbliżone do żadnej z pozostałych. Daje to wynik 5
dla n = 2
.
Dla n = 3
pełnej listy odrębnych sekwencji odległość Hamminga jest:
[(0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 2), (0, 2, 3), (0, 3, 0), (0, 3, 1), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 0), (1, 3, 1), (1, 3, 2), (2, 0, 1), (2, 0, 2), (2, 0, 3), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 0), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 0, 2), (3, 0, 3), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 2, 0), (3, 2, 1), (3, 2, 2), (3, 3, 2), (3, 3, 3)]
Z tych 48
sekwencji możemy wybrać zestaw wielkości 21
, aby żadna para w tym zestawie nie była blisko siebie.
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.
Moja maszyna Czasy zostaną uruchomione na moim komputerze 64-bitowym. Jest to standardowa instalacja ubuntu z 8 GB pamięci RAM, ośmiordzeniowym procesorem AMD FX-8350 i Radeon HD 4250. Oznacza to również, że muszę mieć możliwość uruchomienia kodu.
Wiodąca odpowiedź
- Wynik 4 dla 2, 5, 21, 83, 361 autorstwa Christiana Sieversa. C ++
- Ocena 5 dla 2, 5, 21, 83, 372 przez fəˈnɛtɪk. JavaScript
Odpowiedzi:
C ++ przy użyciu biblioteki igraph
Dziękujemy za miłą okazję do nauki nowej biblioteki!
Ten program oblicza teraz
2, 5, 21, 83, 361
szybko. Możesz kontrolować drukowanie węzłów za pomocąPRINTNODES
stałej.Zastosowany wykres ma dodatkowe krawędzie między węzłami odpowiadające wektorom odległości, w których jeden jest blisko (ale nie równy) względem drugiego odwróconego. Przyspiesza to obliczenia, a każdy znaleziony niezależny zestaw jest oczywiście jednym z oryginalnych wykresów. Ponadto, nawet jeśli nie jest to w pełni wymuszone, obliczony niezależny zestaw jest zamykany podczas cofania. Wierzę, że zawsze istnieje maksymalny niezależny zestaw z tą właściwością. Przynajmniej jest jeden dla
n<=4
. (Jestem pewien, że mogę wykazać, że 83 jest optymalny.)Aby skompilować na Debianie, zainstaluj
libigraph0-dev
i wykonajg++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph
.Stary opis:
Biblioteka igraph ma funkcję obliczania maksymalnego rozmiaru niezależnego zestawu wierzchołków wykresu. Potrafi poradzić sobie z tym problemem
n=3
w niecałą sekundę i nie wygasa za kilka dnin=4
.Więc to, co robię, to rozkładam wykres na połączone komponenty i pozwalam bibliotece obsługiwać małe
MAXDIRECT
komponenty (mniejsze niż węzły). W przypadku innych komponentów wybieram wierzchołek i usuwam go. W najlepszym przypadku dzieli to wykres na kilka składników, ale zazwyczaj nie. W każdym razie komponenty (może tylko jeden) są mniejsze i możemy użyć rekurencji.Oczywiście wybór wierzchołka jest ważny. Po prostu biorę jeden z maksymalnych stopni. Przekonałem się, że uzyskuję lepszy wynik (ale tylko w przypadku
n=4
), gdy używam odwróconej listy węzłów. To wyjaśnia magiczną częśćconstruct
funkcji.Może być warto, poprawiając wybór. Ale ważniejsze wydaje się ponowne rozważenie usuniętych węzłów. W tej chwili nigdy więcej na nich nie patrzę. Niektóre z nich mogą być niepodłączone do żadnego z wybranych węzłów. Problem polega na tym, że nie wiem, które węzły tworzą niezależny zestaw. Po pierwsze, usunięcie węzłów przenumeruje pozostałe węzły. Można temu zaradzić, dołączając do nich atrybuty. Co gorsza, obliczenie liczby niepodległości po prostu podaje tę liczbę. Najlepszą alternatywą, jaką oferuje biblioteka, jest obliczenie wszystkich największych niezależnych zestawów, która jest wolniejsza (ile wydaje się zależeć od wielkości wykresu). Wydaje się jednak, że jest to najbliższa droga. O wiele bardziej niejasne wydaje mi się, że warto rozważyć, czy możemy użyć specjalnego sposobu definiowania wykresu.
Sprawa
n=6
może być osiągalna (wcale, niekoniecznie za 5 minut), jeśli zastąpię rekurencję pętlą, używając kolejki dla pozostałych składników.Interesujące było dla mnie spojrzenie na składniki wykresów. Ponieważ
n=4
ich rozmiary to168, 2*29, 2*28, 3, 4*2, 4*1
. Tylko największego nie da się obsłużyć bezpośrednio.Dla
n=5
, rozmiary są1376, 2*128, 2*120, 119, several <=6
.Oczekuję, że te podwójne rozmiary będą odpowiadały grafom izomorficznym, ale używanie tego nie wydaje się opłacalne, ponieważ zawsze istnieje jeden dominujący największy składnik:
Ponieważ
n=6
największy komponent zawiera11941
węzły (łącznie15425
), kolejne dwa największe komponenty mają rozmiar596
.Na
n=7
te numery są107593 (125232), 2647
.źródło
g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o sievers sievers.cpp -ligraph
. Ma znaczenie, gdzie-ligraph
jest.set
I, aby uniknąć duplikatów, ale nawet nie pomyślałem o ich kolejności, kiedy napisałem ten kod. Wewnętrzna pętla, która zaczyna się od, poi+1
prostu unika patrzenia na parę, a także na jej zamienioną wersję, która nie jest potrzebna, i jest najłatwiejszym sposobem uniknięcia pętli (krawędzi(a,a)
). To nie zależy od kolejności, w jakiej przychodzą węzły, nie obchodzi mnie, czy dostanę(a,b)
lub(b,a)
.JavaScript, Seq: 2,5,21,
818337267349Udało mi się zwiększyć wartość 4 za pomocą losowego usuwania elementów na początku mojego wyszukiwania. Co dziwne, usunięcie 20 elementów z więcej niż 6 połączeniami było szybsze niż usunięcie 5 elementów z więcej niż 8 połączeniami ...
Ta sekwencja prawdopodobnie nie jest optymalna dla 5 i może nie być optymalna dla 4. Żaden z węzłów nie jest jednak zbliżony do drugiego w zestawie.
Kod:
Wypróbuj online!
Fragment, który można dodać na końcu programu, aby pokazać, jakie sekwencje odległości Hamminga wybrana sekwencja odległości Hamminga
Wyjaśnienie:
Po pierwsze, kod generuje wszystkie unikalne odległości uderzenia od podciągów.
Następnie kod konwertuje tę listę na niekierowany wykres
Na koniec kod przechodzi przez ten wykres, usuwając wierzchołek z największą liczbą połączeń w każdym cyklu przed przywróceniem jakichkolwiek węzłów, które miałyby teraz mniej połączeń niż obecne maksimum. Po zakończeniu tego cyklu wyświetla liczbę pozostałych węzłów
Zestawy:
1:
2:
3:
4:
5:
źródło