[Dies ist eine Partnerfrage, um eine Wahrscheinlichkeit genau zu berechnen ]
Bei dieser Aufgabe geht es darum, Code zu schreiben, um eine Wahrscheinlichkeit genau und schnell zu berechnen . Die Ausgabe sollte eine genaue Wahrscheinlichkeit sein, die als Bruch in ihrer am meisten reduzierten Form geschrieben wird. Das heißt, es sollte nie ausgegeben werden 4/8
, sondern 1/2
.
n
Betrachten Sie für eine positive Ganzzahl eine gleichmäßig zufällige Zeichenfolge mit einer Länge von 1s und -1s n
und nennen Sie sie A. Verketten Sie nun mit A
ihrem ersten Wert. Das heißt, A[1] = A[n+1]
wenn die Indizierung von 1. A
jetzt Länge hat n+1
. Nun auch eine zweite zufällige Zeichenfolge der Länge betrachten , n
deren erste n
Werte -1, 0 oder 1 , mit einer Wahrscheinlichkeit von 1 / 4,1 / 2, 1/4 und jedes nennen es B.
Betrachten Sie nun das innere Produkt von A[1,...,n]
und B
und das innere Produkt von A[2,...,n+1]
und B
.
Betrachten Sie zum Beispiel n=3
. Mögliche Werte für A
und B
könnten A = [-1,1,1,-1]
und sein B=[0,1,-1]
. In diesem Fall sind die beiden inneren Produkte 0
und 2
.
Ihr Code muss die Wahrscheinlichkeit ausgeben, dass beide inneren Produkte Null sind.
Wenn wir die von Martin Büttner erstellte Tabelle kopieren, erhalten wir die folgenden Beispielergebnisse.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Sprachen und Bibliotheken
Sie können jede frei verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Ich muss in der Lage sein, Ihren Code auszuführen. Bitte geben Sie eine vollständige Erklärung an, wie Sie Ihren Code unter Linux ausführen / kompilieren können, wenn dies überhaupt möglich ist.
Die Aufgabe
Ihr Code muss mit beginnen n=1
und die richtige Ausgabe für jedes zunehmende n in einer separaten Zeile angeben. Es sollte nach 10 Sekunden aufhören.
Die Punktzahl
Die Punktzahl ist einfach die höchste, die n
erreicht wird, bevor Ihr Code nach 10 Sekunden auf meinem Computer stoppt. Wenn es ein Unentschieden gibt, ist der Gewinner derjenige, der am schnellsten die höchste Punktzahl erreicht.
Tabelle der Einträge
n = 64
in Python . Version 1 von Mitch Schwartzn = 106
in Python . Version 11. Juni 2015 von Mitch Schwartzn = 151
in C ++ . Port of Mitch Schwartz 'Antwort von kirbyfan64sosn = 165
in Python . Version 11. Juni 2015 die "Schnitt" -Version von Mitch Schwartz mitN_MAX = 165
.n = 945
in Python von Min_25 mit einer genauen Formel. Tolle!n = 1228
in Python von Mitch Schwartz unter Verwendung einer anderen exakten Formel (basierend auf der vorherigen Antwort von Min_25).n = 2761
in Python von Mitch Schwartz mit einer schnelleren Implementierung derselben exakten Formel.n = 3250
in Python mit Pypy von Mitch Schwartz mit der gleichen Implementierung. Diese Punktzahl musspypy MitchSchwartz-faster.py |tail
vermeiden, dass die Konsole über den Bildlauf blättert.
quelle
Antworten:
Python
Eine geschlossene Formel von
p(n)
istEine exponentielle Erzeugungsfunktion von
p(n)
istwo
I_0(x)
ist die modifizierte Bessel-Funktion der ersten Art.Bearbeiten am 11.06.2015:
- Der Python-Code wurde aktualisiert.
Bearbeiten am 13.06.2015:
- Ein Beweis für die obige Formel wurde hinzugefügt.
- behoben die
time_limit
.- einen PARI / GP-Code hinzugefügt.
Python
PARI / GP
Beweis:
Dieses Problem ähnelt einem zweidimensionalen (eingeschränkten) Random-Walk-Problem.
Wenn
A[i] = A[i+1]
, können wir aus bewegen(x, y)
zu(x+1, y+1)
[1 Art und Weise],(x, y)
[2 Wegen] oder(x-1, y-1)
[1 Art und Weise].Wenn
A[i] != A[i+1]
, können wir aus bewegen(x, y)
zu(x-1, y+1)
[1 Art und Weise],(x, y)
[2 Wegen] oder(x+1, y-1)
[1 Art und Weise].Lassen Sie
a(n, m) = [x^m]((x+1)^n + (x-1)^n)
,b(n) = [x^n](1+x)^{2n}
undc(n)
kann die Anzahl der Möglichkeiten , von sich zu bewegen ,(0, 0)
um(0, 0)
mitn
Schritten.Dann,
c(n) = \sum_{i=0}^n a(n, i) * b(i) * b(n-i).
Da
p(n) = c(n) / 8^n
können wir die obige Formel in geschlossener Form erhalten.quelle
Python
Hinweis: Herzlichen Glückwunsch an Min_25 zur Suche nach einer geschlossenen Lösung!
Danke für das interessante Problem! Es kann mit DP gelöst werden, obwohl ich mich derzeit nicht sehr motiviert fühle, die Geschwindigkeit zu optimieren, um eine höhere Punktzahl zu erzielen. Es könnte schön zum Golfen sein.
Der Code erreichte
N=39
innerhalb von 10 Sekunden auf diesem alten Laptop mit Python 2.7.5.Für Tupel
(a,b,s,t)
:a
ist das erste Element vonA
,b
ist das letzte Element vonB
,s
ist das innere Produkt vonA[:-1]
undB
undt
ist das innere Produkt vonA[1:-1]
undB[:-1]
unter Verwendung der Python-Slice-Notation. Mein Code speichert nicht die ArraysA
oderB
überall, so dass ich diese Briefe verwenden , um die nächsten Elemente beziehen hinzugefügt werdenA
undB
sind. Diese Wahl der Variablennamen macht die Erklärung etwas umständlich, ermöglicht jedoch ein ansprechendes AussehenA*b+a*B
im Code selbst. Beachten Sie, dass das hinzugefügte ElementA
das vorletzte ist, da das letzte Element immer das gleiche ist wie das erste. Ich habe Martin Büttners Trick angewendet,0
zweimal dabei zu seinB
Kandidaten, um die richtige Wahrscheinlichkeitsverteilung zu erhalten. Das WörterbuchX
(die NamenY
fürN+1
entsprechend den Wert des Tupels) hält die Zählung aller möglichen Arrays verfolgen. Die Variablenn
undd
stehen für Zähler und Nenner, weshalb ich dien
der Problemstellung in umbenannt habeN
.Der wichtigste Teil der Logik ist , dass Sie aus aktualisieren können ,
N
umN+1
mit nur die Werte im Tupel. Die beiden in der Frage angegebenen inneren Produkte sind durchs+A*B
und gegebent+A*b+a*B
. Dies ist klar, wenn Sie die Definitionen ein wenig untersuchen. beachten Sie, dass ,[A,a]
und[b,B]
die letzten beiden Elemente des ArraysA
undB
jeweils.Beachten Sie, dass
s
undt
klein und begrenztN
sind. Für eine schnelle Implementierung in einer schnellen Sprache könnten wir Wörterbücher zugunsten von Arrays vermeiden.Es kann möglich sein, die Symmetrie zu nutzen, wenn Werte berücksichtigt werden, die sich nur im Vorzeichen unterscheiden. Ich habe das nicht untersucht.
Bemerkung 1 : Die Größe des Wörterbuchs wächst quadratisch
N
, wobei Größe die Anzahl der Schlüssel-Wert-Paare bedeutet.Bemerkung 2 : Wenn wir eine Obergrenze festlegen
N
, können wir Tupel beschneiden, für dieN_MAX - N <= |s|
und in ähnlicher Weise fürt
. Dies könnte durch Angabe eines absorbierenden Zustands oder implizit mit einer Variablen erfolgen, die die Anzahl der beschnittenen Zustände enthält (die bei jeder Iteration mit 8 multipliziert werden müssten).Update : Diese Version ist schneller:
Optimierungen implementiert:
main()
- lokaler Variablenzugriff ist schneller als globalN=1
explizit den Scheck zu vermeiden(1,-1) if N else [a]
(was die in dem Tupel das erste Element erzwingt konsistent ist, wenn die Elemente auf dem HinzufügenA
ausgehend von der leeren Liste)c
für das Hinzufügen von a0
zu,B
anstatt diese Vorgänge zweimal auszuführen8^N
so, dass wir ihn nicht im Auge behalten müssenA
as festlegen1
und den Nenner durch dividieren2
, da die gültigen Paare(A,B)
mitA[1]=1
und diejenigen mitA[1]=-1
durch Negieren in eine Eins-zu-Eins-Entsprechung gebracht werden könnenA
. Ebenso können wir das erste ElementB
als nicht negativ festlegen .N_MAX
zu sehen, welche Punktzahl auf Ihrem Computer erzielt werden kann. Es könnte umgeschrieben werden, umN_MAX
automatisch eine geeignete durch binäre Suche zu finden, aber scheint unnötig? Hinweis: Wir müssen den Bereinigungszustand erst überprüfen, wennN_MAX / 2
wir ihn erreichen , damit wir durch Iteration in zwei Phasen ein wenig schneller werden können. Ich habe mich jedoch aus Gründen der Einfachheit und Code-Sauberkeit dagegen entschieden.quelle
N=57
für die erste Version undN=75
für die zweite.Python
Mit Min_25s Idee des zufälligen Gehens konnte ich zu einer anderen Formel gelangen:
Hier ist eine Python-Implementierung, die auf Min_25 basiert:
Erklärung / Beweis:
Zuerst lösen wir ein verwandtes Zählproblem, wo wir es zulassen
A[n+1] = -A[1]
; Das heißt, das zusätzliche Element, mit dem verkettet ist,A
kann1
oder-1
unabhängig vom ersten Element sein. Wir müssen also nicht verfolgen, wie oft esA[i] = A[i+1]
vorkommt. Wir haben den folgenden zufälligen Spaziergang:Von können
(x,y)
wir zu(x+1,y+1)
[1 Weg],(x+1,y-1)
[1 Weg],(x-1,y+1)
[1 Weg],(x-1,y-1)
[1 Weg],(x,y)
[4 Wege] übergehen.wo
x
undy
stehen für die beiden Punktprodukte, und wir zählen die Anzahl der Wege, um schrittweise von(0,0)
nach(0,0)
zu gelangenn
. Diese Zählung würde dann mit multipliziert2
, um die Tatsache zu berücksichtigen, dassA
mit1
oder beginnen kann-1
.Wir bezeichnen das Bleiben
(x,y)
als Nullbewegung .Wir iterieren über die Anzahl der Züge ungleich Null
i
, die gerade sein muss, um zurück zu kommen(0,0)
. Horizontale und vertikale Bewegungen bilden zwei unabhängige eindimensionale Zufallsbewegungen, die gezählt werden könnenC(i,i/2)^2
, wobei derC(n,k)
Binomialkoeffizient ist. (Bei einem Spaziergang mitk
Schritten nach links und nachk
rechts gibt esC(2k,k)
Möglichkeiten, die Reihenfolge der Schritte zu wählen.) Zusätzlich gibt esC(n,i)
Möglichkeiten, die Bewegungen zu platzieren und die4^(n-i)
Nullbewegungen auszuwählen. So bekommen wir:Nun müssen wir zum ursprünglichen Problem zurückkehren. Definieren Sie ein zulässiges Paar
(A,B)
, das konvertierbar sein soll , wenn esB
eine Null enthält. Definieren Sie ein Paar so(A,B)
, dass es fast zulässig ist, wennA[n+1] = -A[1]
und die beiden Punktprodukte beide Null sind.Lemma: Für eine gegebene Zeit
n
stimmen die fast zulässigen Paare eins zu eins mit den konvertierbaren Paaren überein.Wir können ein reversibles Paar (reversibel)
(A,B)
in ein fast zulässiges Paar umwandeln, indem wir(A',B')
negierenA[m+1:]
undB[m+1:]
wom
ist der Index der letzten Null inB
. Die Überprüfung hierfür ist unkompliziert: Wenn das letzte Element vonB
Null ist, müssen wir nichts tun. Andernfalls können wir, wenn wir das letzte Element von negieren, das letzte Element vonA
negierenB
, um den letzten Term des verschobenen Punktprodukts beizubehalten. Dies negiert jedoch den letzten Wert des nicht verschobenen Punktprodukts, sodass wir dies beheben, indem wir das vorletzte Element von negierenA
. Aber dann wirft dies den vorletzten Wert des verschobenen Produkts ab, sodass wir das vorletzte Element von negierenB
. Und so weiter, bis ein Nullelement erreicht istB
.Jetzt müssen wir nur zeigen, dass es keine fast zulässigen Paare gibt, für die
B
keine Null enthalten ist. Damit ein Punktprodukt gleich Null ist, müssen wir die gleiche Anzahl1
und-1
Begriffe haben, die aufgehoben werden sollen. Jeder-1
Begriff besteht aus(1,-1)
oder(-1,1)
. Die Parität der Anzahl-1
dieser Vorkommen ist also entsprechend festgelegtn
. Wenn das erste und das letzte ElementA
unterschiedliche Vorzeichen haben, ändern wir die Parität, sodass dies unmöglich ist.Also bekommen wir
Dies ergibt die obige Formel (Neuindizierung mit
i' = i/2
).Update: Hier ist eine schnellere Version mit der gleichen Formel:
Optimierungen implementiert:
p(n)
C(n,k)
mitk <= n/2
quelle
p(n)
muss es keine stückweise Funktion sein. Im Allgemeinen könnenf(n) == {g(n) : n is odd; h(n) : n is even}
Sie dann schreibenf(n) == (n-2*floor(n/2))*g(n) + ((n+1)-2*(floor((n+1)/2)))*h(n)
oder verwenden,n mod 2
anstatt(n-2*floor(n/2))
. Siehe hierErklärung der Min_25-Formel
Min_25 hat einen großartigen Beweis veröffentlicht, aber es hat eine Weile gedauert, bis er folgte. Dies ist eine Erklärung, die zwischen den Zeilen eingefügt werden muss.
a (n, m) gibt die Anzahl der Möglichkeiten an, A so zu wählen, dass A [i] = A [i + 1] m mal ist. Die Formel für a (n, m) entspricht a (n, m) = {2 * (n wähle m) für nm gerade; 0 für ungerade nm.} Es ist nur eine Parität zulässig, da A [i]! = A [i + 1] gerade oft auftreten muss, damit A [0] = A [n]. Der Faktor 2 ergibt sich aus der anfänglichen Wahl A [0] = 1 oder A [0] = -1.
Sobald die Anzahl von (A [i]! = A [i + 1]) auf q festgelegt ist (in der c (n) -Formel mit i bezeichnet), wird sie in zwei 1D-Zufallsläufe der Länge q und nq aufgeteilt. b (m) ist die Anzahl der Wege, um einen eindimensionalen zufälligen Spaziergang von m Schritten zu machen, der an der Stelle endet, an der er begonnen hat, und hat eine Chance von 25%, sich nach links zu bewegen, eine Chance von 50%, still zu bleiben, und eine Chance von 25% nach rechts bewegen. Ein offensichtlicherer Weg, die Erzeugungsfunktion anzugeben, ist [x ^ m] (1 + 2x + x ^ 2) ^ n, wobei 1, 2x und x ^ 2 links, keine Bewegung bzw. rechts darstellen. Aber dann ist 1 + 2x + x ^ 2 = (x + 1) ^ 2.
quelle
C ++
Nur eine Portierung der (ausgezeichneten) Python-Antwort von Mitch Schwartz. Der primäre Unterschied ist , dass ich verwendet
2
zur Darstellung-1
für diea
Variable und tat etwas ähnliches fürb
, die mir erlaubt , eine Anordnung zu verwenden. Mit Intel C ++ mit habe-O3
ichN=141
! Meine erste Version bekamN=140
.Dies verwendet Boost. Ich habe eine parallele Version ausprobiert, bin aber auf Probleme gestoßen.
quelle
g++ -O3 kirbyfan64sos.cpp -o kirbyfan64sos -lboost_system -lboost_timer -lboost_chrono -lrt -lgmp
kompiliert werden. (Danke an aditsu.)