Der Hamming-Abstand zwischen zwei Saiten gleicher Länge ist die Anzahl der Positionen, an denen sich die entsprechenden Symbole unterscheiden.
Sei P
eine binäre Zeichenkette der Länge n
und T
sei eine binäre Zeichenkette der Länge 2n-1
. Wir können die n
Hamming-Abstände zwischen P
und für jeden n
-langen Teilstring T
in der Reihenfolge von links nach rechts berechnen und sie in ein Array (oder eine Liste) einfügen .
Beispiel Hamming-Distanz-Sequenz
Lass P = 101
und T = 01100
. Die Reihenfolge der Hamming-Abstände, die Sie von diesem Paar erhalten, ist 2,2,1
.
Definition von Nähe
Betrachten wir nun zwei solcher Sequenzen von Hamming-Entfernungen. Sagen Sie x = (0, 2, 2, 3, 0)
und y = (2, 1, 4, 4, 2)
als Beispiele. Wir sagen das x
und y
sind close
ob y <= x <= 2*y
oder ob x <= y <= 2*x
. Hier werden die Skalarmultiplikation und die Ungleichung elementweise genommen. Das heißt, für zwei Sequenzen A
und B
, A <= B iff A[i] <= B[i]
für alle Indizes i
.
Man beachte , dass Sequenzen von Hamming - Abstände bilden eine Teilordnung im Rahmen dieser Weise , sie zu vergleichen. Mit anderen Worten, viele Paare von Sequenzen sind weder größer oder gleich noch kleiner oder gleich zueinander. Zum Beispiel (1,2)
und (2,1)
.
Also anhand des obigen Beispiels, ist (0, 2, 2, 3, 0) <= 2*(2, 1, 4, 4, 2) = (4, 2, 8, 8, 4)
aber (0, 2, 2, 3, 0)
nicht größer als (2, 1, 4, 4, 2)
. Auch (2, 1, 4, 4, 2)
ist nicht kleiner als oder gleich 2*(0, 2, 2, 3, 0) = (0, 4, 4, 6, 0)
. Infolgedessen x
und y
nicht nah beieinander.
Aufgabe
Berücksichtigen Sie zum Erhöhen n
ab n=1
alle möglichen Paare von binären Zeichenfolgen P
der Länge n
und T
der Länge 2n-1
. Es gibt 2^(n+2n-1)
solche Paare und damit viele Sequenzen von Hamming-Abständen. Viele dieser Sequenzen sind jedoch identisch. Die Aufgabe besteht darin, die Größe des größten Satzes von Hamming-Distanzsequenzen zu ermitteln, sodass keine zwei Sequenzen nahe beieinander liegen.
Ihr Code sollte eine Zahl pro Wert von ausgeben n
.
Ergebnis
Ihre Punktzahl ist im Großen und Ganzen die höchste, die n
Ihr Code in 5 Minuten auf meinem Computer erreicht (aber lesen Sie weiter). Das Timing bezieht sich auf die Gesamtlaufzeit, nicht nur auf die Zeit dafür n
.
Um nicht optimale Antworten bewerten zu können, benötigen wir ein etwas subtiles Bewertungssystem, da es wahrscheinlich schwierig ist, optimale Antworten zu finden. Ihre Punktzahl ist der höchste Wert, n
für den niemand eine höhere richtige Antwort für eine Größe veröffentlicht hat, die kleiner als diese ist. Wenn Sie beispielsweise ausgeben 2, 4, 21
und jemand anderes ausgeben , 2, 5, 15
erzielen Sie nur ein Ergebnis, 1
wenn jemand anderes eine bessere Antwort auf diese Frage hat n = 2
. Wenn Sie ausgeben 2, 5, 21
, würden Sie 3
unabhängig von den Ausgaben anderer Punkte erzielen , da diese Antworten alle optimal sind. Wenn Sie alle optimalen Antworten haben, erhalten Sie die Punktzahl für den höchsten n
Beitrag, den Sie verfassen. Aber auch wenn Ihre Antwort nicht optimal ist, können Sie die Punktzahl erhalten, wenn niemand anders sie schlagen kann.
Beispielantworten und bearbeitetes Beispiel
(Diese Antwort ist noch nicht angekreuzt. Eine unabhängige Überprüfung wäre dankbar.)
Dank ETHproductions:
- n = 1 ergibt 2.
- n = 2 ergibt 5.
- n = 3 ergibt 21.
Schauen wir uns das n = 2
genauer an. In diesem Fall lautet die vollständige Liste der Hamming-Distanzsequenzen (hier durch Tupel dargestellt):
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
Wir können sehen, dass dies (0,0)
keinem anderen Tupel nahe kommt. In der Tat , wenn wir annehmen (0, 0)
, (0, 1)
, (1, 0)
, (2, 1)
, (1,2)
dann keines dieser Tupel ist in der Nähe zu einem anderen. Dies ergibt eine Punktzahl von 5
für n = 2
.
Für n = 3
die vollständige Liste der deutlichen Hamming - Distanz - Sequenzen ist:
[(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)]
Von diesen 48
Sequenzen können wir eine Menge von Größen auswählen, 21
so dass kein Paar in dieser Menge nahe beieinander liegt.
Sprachen und Bibliotheken
Sie können jede verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Wo immer möglich, wäre es gut, wenn Sie Ihren Code ausführen könnten. Fügen Sie daher bitte eine vollständige Erklärung dazu bei, wie Sie Ihren Code unter Linux ausführen / kompilieren, wenn dies überhaupt möglich ist.
Mein Computer Die Timings werden auf meinem 64-Bit-Computer ausgeführt. Dies ist eine Ubuntu-Standardinstallation mit 8 GB RAM, AMD FX-8350 Eight-Core-Prozessor und Radeon HD 4250. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen.
Führende Antwort
- Score von 4 für 2, 5, 21, 83, 361 von Christian Sievers. C ++
- Score von 5 für 2, 5, 21, 83, 372 von fəˈnəˈtɛk. Javascript
Antworten:
C ++ mit der igraph Bibliothek
Vielen Dank für eine schöne Gelegenheit, eine neue Bibliothek zu lernen!
Dieses Programm berechnet jetzt
2, 5, 21, 83, 361
schnell. Sie können das Drucken der Knoten mit derPRINTNODES
Konstante steuern .Das verwendete Diagramm weist zusätzliche Kanten zwischen Knoten auf, die Distanzvektoren entsprechen, von denen einer in der Nähe (aber nicht gleich) des anderen in umgekehrter Richtung liegt. Das beschleunigt die Berechnung, und jede gefundene unabhängige Menge ist natürlich auch eine der Originalgraphen. Auch wenn es nicht vollständig erzwungen wird, wird die berechnete unabhängige Menge unter Umkehrung geschlossen. Ich glaube, es gibt immer eine maximale unabhängige Menge mit dieser Eigenschaft. Zumindest gibt es eine für
n<=4
. (Ich bin sicher, ich kann zeigen, dass 83 optimal ist.)Um unter Debian zu kompilieren, installieren Sie
libigraph0-dev
und tung++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph
.Alte Beschreibung:
Die Igraph-Bibliothek hat eine Funktion zum Berechnen der maximalen Größe eines unabhängigen Scheitelpunktsatzes eines Graphen. Es kann mit diesem Problem umgehen
n=3
in weniger als einer Sekunde und endet nicht in Tagen fürn=4
.Ich zerlege also den Graphen in verbundene Komponenten und überlasse der Bibliothek den Umgang mit dem kleinen (kleiner als
MAXDIRECT
Knoten) Komponenten . Für die anderen Komponenten wähle ich einen Eckpunkt aus und lösche ihn. Im besten Fall wird das Diagramm dadurch in mehrere Komponenten aufgeteilt, in der Regel jedoch nicht. Wie auch immer, die Komponenten (vielleicht nur eine) sind kleiner und wir können die Rekursion verwenden.Offensichtlich ist die Auswahl des Scheitelpunkts wichtig. Ich nehme nur einen von maximalem Grad. Ich habe festgestellt, dass ich ein besseres Ergebnis bekomme (aber nur für
n=4
), wenn ich eine umgekehrte Knotenliste verwende. Das erklärt den magischen Teil derconstruct
Funktion.Es könnte sich lohnen, die Auswahl zu verbessern. Wichtiger erscheint es jedoch, die gelöschten Knoten zu überdenken. Im Moment schaue ich sie nie wieder an. Einige von ihnen sind möglicherweise nicht mit einem der ausgewählten Knoten verbunden. Das Problem ist, dass ich nicht weiß, welche Knoten die unabhängige Menge bilden. Zum einen werden beim Löschen von Knoten die verbleibenden Knoten neu nummeriert. Dies kann durch Anhängen von Attributen erledigt werden. Schlimmer noch, die Berechnung der Unabhängigkeitszahl ergibt nur diese Zahl. Die beste Alternative, die die Bibliothek bietet, besteht darin, alle größten unabhängigen Mengen zu berechnen , was langsamer ist (wie viel davon anscheinend von der Diagrammgröße abhängt). Dies scheint jedoch der unmittelbare Weg zu sein. Viel vager halte ich es auch für sinnvoll, zu prüfen, ob wir die spezielle Art und Weise verwenden können, in der das Diagramm definiert ist.
Der Fall wird
n=6
möglicherweise erreichbar (nicht unbedingt in 5 Minuten), wenn ich die Rekursion durch eine Schleife ersetze, die eine Warteschlange für die übrigen Komponenten verwendet.Ich fand es interessant, die Komponenten der Grafiken zu betrachten. Denn
n=4
ihre Größen sind168, 2*29, 2*28, 3, 4*2, 4*1
. Nur der größte kann nicht direkt gehandhabt werden.Denn
n=5
die Größen sind1376, 2*128, 2*120, 119, several <=6
.Ich erwarte, dass diese doppelten Größen isomorphen Graphen entsprechen, aber es lohnt sich nicht, sie zu verwenden, da es immer eine einzige dominierende größte Komponente gibt:
Denn
n=6
die größte Komponente enthält11941
Knoten (von insgesamt15425
), die nächsten beiden größten Komponenten haben eine Größe596
.Denn
n=7
diese Zahlen sind107593 (125232), 2647
.quelle
g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o sievers sievers.cpp -ligraph
. Es ist wichtig, wo-ligraph
ist.set
ich verwende, um Duplikate zu vermeiden, aber ich habe nicht einmal an ihre Reihenfolge gedacht, als ich diesen Code geschrieben habe. Die innere Schleife, die bei beginnt,i+1
vermeidet das Betrachten eines Paares und auch die vertauschte Version, die nicht benötigt wird, und ist der einfachste Weg, um Schleifen (Kanten(a,a)
) zu vermeiden . Es hängt nicht von der Reihenfolge ab, in der die Knoten kommen. Es ist mir egal, ob ich(a,b)
oder bekomme(b,a)
.Javascript, Seq: 2,5,21,
81,83,372, 67,349Es ist mir gelungen, den Wert für 4 durch zufälliges Entfernen von Elementen zu Beginn meiner Suche zu erhöhen. Seltsamerweise war das Entfernen von 20 Elementen mit mehr als 6 Verbindungen schneller als das Entfernen von 5 Elementen mit mehr als 8 Verbindungen ...
Diese Sequenz ist wahrscheinlich nicht optimal für 5 und möglicherweise nicht optimal für 4. Keiner der Knoten befindet sich jedoch in der Menge in der Nähe eines anderen.
Code:
Probieren Sie es online!
Ausschnitt, der am Ende des Programms hinzugefügt werden kann, um anzuzeigen, welche Hamming-Distanzsequenzen für jede ausgewählte Hamming-Distanzsequenz gelten
Erläuterung:
Zunächst generiert der Code alle eindeutigen Hamming-Abstände von den Teilzeichenfolgen.
Als nächstes konvertiert der Code diese Liste in ein ungerichtetes Diagramm
Schließlich durchläuft der Code dieses Diagramm und entfernt den Scheitelpunkt mit den meisten Verbindungen in jedem Zyklus, bevor Knoten wiederhergestellt werden, die jetzt weniger Verbindungen als das aktuelle Maximum haben würden. Wenn dieser Zyklus beendet ist, wird die Anzahl der verbleibenden Knoten ausgegeben
Sätze:
1:
2:
3:
4:
5:
quelle