n
Berücksichtigen Sie für eine bestimmte positive Ganzzahl alle binären Zeichenfolgen mit der Länge 2n-1
. S
Sei für einen gegebenen String L
ein Array von Länge, n
das die Anzahl der 1
s in jedem Teilstring von Länge n
von enthält S
. Zum Beispiel, wenn n=3
und S = 01010
dann L=[1,2,1]
. Wir nennen L
das Zählarray von S
.
Wir sagen , dass zwei Strings S1
und S2
die gleiche Länge Spiel , wenn ihre jeweiligen Zählen Arrays L1
und L2
haben die Eigenschaft , dass L1[i] <= 2*L2[i]
und L2[i] <= 2*L1[i]
für alle i
.
Aufgabe
Zum Erhöhen n
ab n=1
besteht die Aufgabe darin, die Größe des größten Satzes von Zeichenfolgen zu finden, wobei jede Länge 2n-1
so ist, dass keine zwei Zeichenfolgen übereinstimmen.
Ihr Code sollte eine Zahl pro Wert von ausgeben n
.
Ergebnis
Ihre Punktzahl ist die höchste, n
für die noch niemand eine richtigere Antwort für eine Ihrer Antworten abgegeben hat. Wenn Sie alle optimalen Antworten haben, erhalten Sie die Punktzahl für den höchsten n
Beitrag, den Sie verfassen. Auch wenn Ihre Antwort nicht optimal ist, können Sie die Punktzahl erhalten, wenn niemand anders sie schlagen kann.
Beispielantworten
Denn n=1,2,3,4
ich verstehe 2,4,10,16
.
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.
Führende Einträge
- 5 von Martin Büttner in Mathematica
- 6 von Reto Koradi in C ++ . Werte sind
2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
. Die ersten 5 sind als optimal bekannt. - 7 von Peter Taylor in Java . Werte sind
2, 4, 10, 16, 31, 47, 76, 111, 166, 235
. - 9 von joriki in Java . Werte sind
2, 4, 10, 16, 31, 47, 76, 112, 168
.
L1[i]/2 <= L2[i] <= 2*L1[i]
.match(A, B)
undmatch(B, C)
impliziert nichtmatch(A, C)
(dasselbe für die Umkehrung). Beispiel: [1] und [2] stimmen überein, [2] und [3] stimmen überein, [1] und [3] jedoch nicht. Ebenso stimmen [1,3] und [3,1] nicht überein, [3, 1] und [2, 3] stimmen nicht überein, aber [1, 3] und [2, 3] stimmen überein.Antworten:
2, 4, 10, 16, 31, 47, 76, 112, 168
Für jedes n bestimmt dieser Java-Code die möglichen Zählarrays und findet dann nicht übereinstimmende Mengen mit zunehmender Größe, wobei jede Größe mit einer zufälligen Menge beginnt und durch zufällige steilste Abnahme verbessert wird. In jedem Schritt wird eines der Elemente des Satzes zufällig gleichmäßig ausgewählt und durch ein anderes Zählarray ersetzt, das zufällig gleichmäßig aus den nicht verwendeten ausgewählt wird. Der Schritt wird akzeptiert, wenn die Anzahl der Übereinstimmungen nicht erhöht wird. Diese letztere Vorschrift scheint entscheidend zu sein; Schritte nur dann zu akzeptieren, wenn sie die Anzahl der Übereinstimmungen verringern, ist bei weitem nicht so effektiv. Die Schritte, bei denen die Anzahl der Übereinstimmungen unverändert bleibt, ermöglichen das Durchsuchen des Suchraums. Schließlich kann sich etwas Platz öffnen, um eine der Übereinstimmungen zu vermeiden. Nach 2 ^ 24 Schritten ohne Verbesserung wird die vorherige Größe für den gegenwärtigen Wert von n ausgegeben und n wird inkrementiert.
Die Ergebnisse bis n = 9
2, 4, 10, 16, 31, 47, 76, 112, 168
verbessern sich gegenüber den vorherigen Ergebnissen für n = 8 um eins und für n = 9 um zwei. Für höhere Werte von n muss die Grenze von 2 ^ 24 Schritten möglicherweise erhöht werden.Ich habe auch simuliertes Tempern versucht (mit der Anzahl der Übereinstimmungen als Energie), aber ohne Verbesserung gegenüber der steilsten Abfahrt.
Code
Speichern als
Question54354.java
Kompilieren mit
javac Question54354.java
Ausführen mit
java Question54354
quelle
2, 4, 10, 16, 31, 47, 76, 111, 166, 235
Anmerkungen
Wenn wir einen Graphen
G
mit Eckpunkten0
zun
und Kanten betrachten, die zwei übereinstimmende Zahlen verbinden, dann hat die Tensor-PotenzG^n
Eckpunkte,(x_0, ..., x_{n-1})
die die kartesische Potenz{0, ..., n}^n
und Kanten zwischen übereinstimmenden Tupeln bilden. Der Graph von Interesse ist der Untergraph vonG^n
induziert durch jene Eckpunkte, die den möglichen "Zählarrays" entsprechen.Die erste Teilaufgabe besteht also darin, diese Eckpunkte zu generieren. Der naive Ansatz zählt über
2^{2n-1}
Strings oder in der Reihenfolge von auf4^n
. Betrachten wir stattdessen das Array der ersten Unterschiede der Zählarrays, so gibt es nur3^n
Möglichkeiten. Aus den ersten Unterschieden können wir den Bereich der möglichen Anfangswerte ableiten, indem wir voraussetzen, dass kein Element in den nullten Unterschieden kleiner als ist0
oder ist größer alsn
.Wir wollen dann die maximale unabhängige Menge finden. Ich benutze einen Satz und zwei Heuristiken:
(n, n, ..., n)
es sich um eine maximale unabhängige Menge handelt. Es gibt eine ziemlich große Gruppe von Eckpunkten, bei{m, m+1, ..., n}^n
denenm
die kleinste Ganzzahl übereinstimmtn
.(n, n, ..., n)
garantiert keine Übereinstimmungen außerhalb dieser Clique.Auf meinem Computer diese Funde
111
fürn=8
16 Sekunden166
fürn=9
in etwa 8 Minuten und235
fürn=10
in etwa 2 Stunden.Code
Speichern als
PPCG54354.java
, Kompilieren alsjavac PPCG54354.java
und Ausführen alsjava PPCG54354
.quelle
Mathematica
n = 5
, 31 SaitenIch schrieb eine Brute - Force - Lösung mit Mathematica eingebauten Ins Lembik des Beispiel Antworten zu überprüfen, aber es kann behandeln
n = 5
auch:Als Bonus erstellt dieser Code eine grafische Darstellung des Problems, wobei jede Kante zwei übereinstimmende Zeichenfolgen angibt.
Hier ist die Grafik für
n = 3
:quelle
C ++ (heuristisch): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
Dies ist etwas hinter Peter Taylors Ergebnis zurück, das für und 1 bis 3 niedriger
n=7
ist . Der Vorteil ist, dass es viel schneller ist, so dass ich es für höhere Werte von ausführen kann . Und es kann ohne ausgefallene Mathematik verstanden werden. ;)9
10
n
Der aktuelle Code ist so dimensioniert, dass er bis zu ausgeführt werden kann
n=15
. Die Laufzeiten erhöhen sich bei jeder Erhöhung von ungefähr um den Faktor 4n
. Zum Beispiel war sie 0,008 Sekunden langn=7
, 0,07 Sekunden langn=9
, 1,34 Sekunden langn=11
, 27 Sekunden langn=13
und 9 Minuten langn=15
.Ich habe zwei wichtige Beobachtungen gemacht:
c
ohne den Bereich vonc / 2
bis2 * c
von anderen Werten. Für kleinere Werte vonc
ist dieser Bereich kleiner, was bedeutet, dass durch die Verwendung weniger Werte ausgeschlossen werden.Generieren Sie eindeutige Zählarrays
Ich habe mich mit aller Kraft an die Arbeit gemacht, alle Werte durchlaufen, das Zählarray für jeden von ihnen generiert und die resultierende Liste eindeutig festgelegt. Dies könnte sicherlich effizienter erfolgen, ist aber für die Werte, mit denen wir arbeiten, gut genug.
Dies geht bei den kleinen Werten extrem schnell. Für die größeren Werte wird der Overhead erheblich. Zum Beispiel verbraucht
n=15
es 75% der gesamten Laufzeit. Dies wäre definitiv ein Bereich, den man sich ansehen sollte, wenn man versucht, viel höher zu steigen alsn=15
. Selbst die Speicherbelegung für die Erstellung einer Liste der Zählarrays für alle Werte würde problematisch.Die Anzahl der eindeutigen Zählarrays beträgt ungefähr 6% der Anzahl der Werte für
n=15
. Diese relative Anzahl wird kleiner, wenn sien
größer wird.Gierige Auswahl von Zählarraywerten
Der Hauptteil des Algorithmus wählt das Zählen von Array-Werten aus der generierten Liste unter Verwendung eines einfachen gierigen Ansatzes aus.
Basierend auf der Theorie, dass die Verwendung von Zählarrays mit kleinen Zählwerten vorteilhaft ist, werden die Zählarrays nach der Summe ihrer Zählwerte sortiert.
Sie werden dann der Reihe nach überprüft und ein Wert wird ausgewählt, wenn er mit allen zuvor verwendeten Werten kompatibel ist. Dies umfasst also einen einzelnen linearen Durchlauf durch die eindeutigen Zählarrays, bei dem jeder Kandidat mit den zuvor ausgewählten Werten verglichen wird.
Ich habe einige Ideen, wie die Heuristik möglicherweise verbessert werden könnte. Dies schien jedoch ein vernünftiger Ausgangspunkt zu sein, und die Ergebnisse sahen recht gut aus.
Code
Dies ist nicht sehr optimiert. Irgendwann hatte ich eine ausgefeiltere Datenstruktur, aber es hätte mehr Arbeit gebraucht, um sie darüber hinaus zu verallgemeinern
n=8
, und der Leistungsunterschied schien nicht sehr erheblich zu sein.quelle
n=4
gedauert. Es könnten=5
mit etwas Geduld beendet haben. Sie müssen eine bessere Backtracking-Strategie angewendet haben, um es überhaupt zu schaffenn=7
. War Ihre Heuristik oder wurde der gesamte Lösungsraum untersucht? Ich denke über einige Ideen nach, wie ich das verbessern kann, entweder indem ich die Sortierreihenfolge verfeinere oder indem ich nicht nur gierig bin.3^n
und die beiden von ihm beschriebenen Heuristiken reduziert .n=7
schnell. Abern=9
als ich es ausprobierte , blieb es immer noch bei 164 stecken, als ich es nach 20 Minuten stoppte. Eine Erweiterung mit einer eingeschränkten Form des einfachen Backtrackings erscheint daher nicht generell vielversprechend.