Diese Frage wurde im Microsoft-Interview gestellt. Sehr neugierig zu wissen, warum diese Leute so seltsame Fragen zur Wahrscheinlichkeit stellen?
Bei einem Rand (N) ein Zufallsgenerator, der eine Zufallszahl von 0 bis N-1 erzeugt.
int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
int m = rand(N);
int n = rand(N);
swap(A[m],A[n]);
}
BEARBEITEN: Beachten Sie, dass der Startwert nicht festgelegt ist.
Wie groß ist die Wahrscheinlichkeit, dass Array A gleich bleibt?
Angenommen, das Array enthält eindeutige Elemente.
algorithm
math
probability
Grüner Kobold
quelle
quelle
N
und einen festen Startwert ist die Wahrscheinlichkeit entweder0
oder1
weil sie überhaupt nicht zufällig ist.swap
Funktion den Inhalt von möglicherweise nicht ändern kannA
. \ edit: Nun,swap
könnte auch ein Makro sein ... hoffen wir nur, dass es nicht so ist :)Antworten:
Nun, ich hatte ein bisschen Spaß mit diesem. Das erste, woran ich dachte, als ich das Problem zum ersten Mal las, war die Gruppentheorie (insbesondere die symmetrische Gruppe S n ). Die for-Schleife baut einfach eine Permutation σ in S n auf, indem sie bei jeder Iteration Transpositionen (dh Swaps) zusammensetzt. Meine Mathematik ist nicht allzu spektakulär und ich bin ein bisschen verrostet. Wenn meine Notation nicht stimmt, nimm sie mit.
Überblick
Sei
A
das Ereignis, dass unser Array nach der Permutation unverändert bleibt. Wir sind schließlich gebeten , die Wahrscheinlichkeit von Ereignis zu findenA
,Pr(A)
.Meine Lösung versucht, das folgende Verfahren zu befolgen:
1) Mögliche Ergebnisse
Beachten Sie, dass jede Iteration der for-Schleife einen Swap (oder eine Transposition ) erzeugt, der eines von zwei Dingen ergibt (aber niemals beide):
Wir kennzeichnen den zweiten Fall. Definieren wir eine Identitätsumsetzung wie folgt:
Für jeden Lauf des aufgelisteten Codes erstellen wir
N
Transpositionen.0, 1, 2, ... , N
In dieser "Kette" können Identitätsumwandlungen auftreten.Betrachten Sie zum Beispiel einen
N = 3
Fall:Beachten Sie, dass es eine ungerade Anzahl von Nichtidentitätstranspositionen gibt (1) und das Array geändert wird.
2) Partitionierung basierend auf der Anzahl der Identitätstranspositionen
Sei
K_i
das Ereignis, dassi
Identitätstranspositionen in einer gegebenen Permutation auftreten. Beachten Sie, dass dies eine vollständige Aufteilung aller möglichen Ergebnisse darstellt:0
undN
Identitätstranspositionen haben.Somit können wir das Gesetz der Gesamtwahrscheinlichkeit anwenden :
Jetzt können wir endlich die Partition nutzen. Beachten Sie, dass das Array bei einer ungeraden Anzahl von Nichtidentitäts- Transpositionen auf keinen Fall unverändert bleiben kann *. So:
* Aus der Gruppentheorie ist eine Permutation gerade oder ungerade, aber niemals beides. Daher kann eine ungerade Permutation nicht die Identitätspermutation sein (da die Identitätspermutation gerade ist).
3) Bestimmen von Wahrscheinlichkeiten
Wir müssen nun zwei Wahrscheinlichkeiten für
N-i
gerade bestimmen :Die erste Amtszeit
Der erste Term repräsentiert die Wahrscheinlichkeit, eine Permutation mit
i
Identitätstranspositionen zu erhalten. Dies stellt sich als binomisch heraus, da für jede Iteration der for-Schleife:1/N
.Daher ist für
N
Versuche die Wahrscheinlichkeit,i
Identitätstranspositionen zu erhalten, wie folgt:Die zweite Amtszeit
Also , wenn Sie es bis hierher geschafft haben, haben wir das Problem zu finden , reduziert für
N - i
selbst. Dies stellt die Wahrscheinlichkeit dar, eine Identitätspermutation zu erhalten, wenni
die Transpositionen Identitäten sind. Ich verwende einen naiven Zählansatz, um die Anzahl der Wege zum Erreichen der Identitätspermutation über die Anzahl möglicher Permutationen zu bestimmen.Betrachten Sie zuerst die Permutationen
(n, m)
und(m, n)
Äquivalente. Dann seiM
die Anzahl der möglichen Nichtidentitätspermutationen. Wir werden diese Menge häufig verwenden.Ziel ist es, die Anzahl der Möglichkeiten zu bestimmen, wie eine Sammlung von Transpositionen kombiniert werden kann, um die Identitätspermutation zu bilden. Ich werde versuchen, die allgemeine Lösung neben einem Beispiel von zu konstruieren
N = 4
.Betrachten wir den
N = 4
Fall bei allen Identitätstranspositionen ( dhi = N = 4
). Stellen wirX
eine Identitätstransposition dar. Für jedenX
gibt esN
Möglichkeiten (sie sind :)n = m = 0, 1, 2, ... , N - 1
. Somit gibt esN^i = 4^4
Möglichkeiten, die Identitätspermutation zu erreichen. Der Vollständigkeit halber addieren wir den BinomialkoeffizientenC(N, i)
, um die Reihenfolge der Identitätstranspositionen zu berücksichtigen (hier ist er nur gleich 1). Ich habe versucht, dies unten mit dem physischen Layout der obigen Elemente und der Anzahl der folgenden Möglichkeiten darzustellen:Jetzt, ohne explizit
N = 4
und zu ersetzeni = 4
, können wir den allgemeinen Fall betrachten. Wenn wir das Obige mit dem zuvor gefundenen Nenner kombinieren, finden wir:Das ist intuitiv. In der Tat sollte Sie jeder andere Wert als
1
wahrscheinlich alarmieren. Denken Sie darüber nach: Wir erhalten die Situation, in der alleN
Transpositionen als Identitäten bezeichnet werden. Was ist wahrscheinlich, dass das Array in dieser Situation unverändert bleibt? Klar ,1
.N = 4
Betrachten wir nun noch einmal zwei Identitätstranspositionen ( dhi = N - 2 = 2
). Als Konvention werden wir die beiden Identitäten am Ende platzieren (und später bestellen). Wir wissen jetzt, dass wir zwei Transpositionen auswählen müssen, die, wenn sie komponiert werden, zur Identitätspermutation werden. Platzieren wir ein Element an der ersten Stelle und nennen est1
. Wie oben erwähnt, gibt esM
Möglichkeiten, vorausgesetzt, est1
handelt sich nicht um eine Identität (es kann nicht so sein, wie wir bereits zwei platziert haben).Das einzige Element, das möglicherweise noch an der zweiten Stelle verbleiben könnte, ist das Inverse von
t1
, was tatsächlich der Fall istt1
(und dies ist das einzige Element aufgrund der Eindeutigkeit des Inversen). Wir schließen wieder den Binomialkoeffizienten ein: In diesem Fall haben wir 4 offene Stellen und wir möchten 2 Identitätspermutationen platzieren. Wie viele Möglichkeiten können wir das tun? 4 wählen Sie 2.Betrachtet man noch einmal den allgemeinen Fall, so entspricht dies alles:
Schließlich machen wir den
N = 4
Fall ohne Identitätstranspositionen ( dhi = N - 4 = 0
). Da es viele Möglichkeiten gibt, wird es schwierig und wir müssen aufpassen, dass wir nicht doppelt zählen. In ähnlicher Weise beginnen wir, indem wir ein einzelnes Element an die erste Stelle setzen und mögliche Kombinationen ausarbeiten. Nehmen Sie die einfachste zuerst: die gleiche Umsetzung 4 Mal.Betrachten wir nun zwei einzigartige Elemente
t1
undt2
. Es gibtM
Möglichkeiten fürt1
und nurM-1
Möglichkeiten fürt2
(dat2
kann nicht gleich seint1
). Wenn wir alle Vorkehrungen ausschöpfen, bleiben uns die folgenden Muster:Betrachten wir nun drei einzigartige Elemente,
t1
,t2
,t3
. Lassen Sie unst1
zuerst und dann platzierent2
. Wie immer haben wir:Wir können noch nicht sagen, wie viele Möglichkeiten
t2
es noch geben kann, und wir werden gleich sehen, warum.Wir platzieren uns jetzt
t1
auf dem dritten Platz. Beachten Sie,t1
dass wir dorthin gehen müssen, da wir, wenn wir an der letzten Stelle hingehen würden, nur das(3)rd
obige Arrangement neu erstellen würden . Doppelzählung ist schlecht! Dadurch bleibt das dritte eindeutige Elementt3
an der endgültigen Position.Warum mussten wir uns eine Minute Zeit nehmen, um die Anzahl der
t2
s genauer zu betrachten ? Die Transpositionent1
undt2
können keine disjunkten Permutationen sein ( dh sie müssen eine (und nur eine, da sie auch nicht gleich sein können) von ihremn
oder teilenm
). Der Grund dafür ist, dass wir die Reihenfolge der Permutationen vertauschen könnten, wenn sie disjunkt wären. Dies bedeutet, dass wir die(1)st
Anordnung doppelt zählen würden .Sagen Sie
t1 = (n, m)
.t2
muss von der Form(n, x)
oder(y, m)
für einige seinx
undy
um nicht disjunkt zu sein. Beachten Sie, dassx
möglicherweise nichtn
oderm
undy
viele nichtn
oder sindm
. Somit ist die Anzahl der möglichen Permutationen,t2
die sein könnten, tatsächlich2 * (N - 2)
.Kommen wir also zu unserem Layout zurück:
Jetzt
t3
muss die Umkehrung der Zusammensetzung von seint1 t2 t1
. Machen wir es manuell:Also
t3
muss sein(m, x)
. Hinweis : Dies ist nicht zu disjunktt1
und nicht entweder gleicht1
odert2
so gibt es keine Doppelzählung für diesen Fall.Zum Schluss noch alles zusammen:
4) Alles zusammenfügen
Das war's. Arbeiten Sie rückwärts und ersetzen Sie das, was wir gefunden haben, durch die ursprüngliche Summe in Schritt 2. Ich habe die Antwort auf den folgenden
N = 4
Fall berechnet . Es stimmt sehr genau mit der empirischen Zahl überein, die in einer anderen Antwort gefunden wurde!Richtigkeit
Es wäre cool, wenn es ein Ergebnis in der Gruppentheorie gäbe, das hier angewendet werden könnte - und vielleicht gibt es das! Es würde sicherlich dazu beitragen, dass all diese mühsamen Zählungen vollständig verschwinden (und das Problem auf etwas viel eleganteres verkürzen). Ich hörte auf zu arbeiten
N = 4
. DennN > 5
was gegeben ist, gibt nur eine Annäherung (wie gut, ich bin nicht sicher). Es ist ziemlich klar, warum das so ist, wenn Sie darüber nachdenken: Zum Beispiel gibt es bei gegebenenN = 8
Transpositionen eindeutig Möglichkeiten, die Identität mit vier einzigartigen Elementen zu schaffen, die oben nicht berücksichtigt wurden. Die Anzahl der Wege wird anscheinend schwieriger zu zählen, wenn die Permutation länger wird (soweit ich das beurteilen kann ...).Jedenfalls konnte ich so etwas im Rahmen eines Interviews definitiv nicht machen. Wenn ich Glück hätte, würde ich bis zum Nenner kommen. Darüber hinaus scheint es ziemlich böse.
quelle
Fragen wie diese werden gestellt, weil sie dem Interviewer ermöglichen, einen Einblick in die des Interviewten zu erhalten
... und so weiter. Der Schlüssel zu einer Frage, die diese Attribute des Befragten enthüllt, ist ein täuschend einfacher Code. Dies schüttelt die Betrüger aus, in denen der Nicht-Codierer steckt. der arrogante Sprung zu der falschen Schlussfolgerung; Der faule oder unterdurchschnittliche Informatiker findet eine einfache Lösung und hört auf zu suchen. Wie sie sagen, geht es oft nicht darum, ob Sie die richtige Antwort erhalten, sondern ob Sie mit Ihrem Denkprozess beeindrucken.
Ich werde auch versuchen, die Frage zu beantworten. In einem Interview würde ich mich erklären, anstatt eine einzeilige schriftliche Antwort zu geben - das liegt daran, dass ich logisches Denken demonstrieren kann, selbst wenn meine „Antwort“ falsch ist.
A bleibt gleich - dh Elemente an den gleichen Positionen - wenn
m == n
in jeder Iteration (so dass jedes Element nur mit sich selbst austauscht); oderDer erste Fall ist der 'einfache' Fall, den duedl0r angibt, der Fall, dass das Array nicht geändert wird. Dies könnte die Antwort sein, weil
Wenn sich das Array bei ändert
i = 1
und dann wieder zurückgesetzt wirdi = 2
, befindet es sich im ursprünglichen Zustand, aber es ist nicht "gleich geblieben" - es wurde geändert und dann wieder geändert. Das könnte eine kluge Technik sein.Wenn ich dann die Möglichkeit in Betracht ziehe, Elemente auszutauschen und zurückzutauschen, denke ich, dass die Berechnung in einem Interview über meinem Kopf liegt. Die offensichtliche Überlegung ist, dass dies keine Änderung sein muss - Wechsel zurück ändern, es könnte genauso gut einen Austausch zwischen drei Elementen geben, 1 und 2, dann 2 und 3, 1 und 3 und schließlich 2 und 3. Und Wenn Sie fortfahren, kann es zu Swaps zwischen 4, 5 oder mehr Elementen kommen, die so "kreisförmig" sind.
In der Tat, nicht die Fälle , in Anbetracht , wo das Array unverändert ist, kann es einfacher sein , die Fälle zu prüfen , wo es wird geändert. Überlegen Sie, ob dieses Problem auf eine bekannte Struktur wie das Pascalsche Dreieck abgebildet werden kann .
Das ist ein schweres Problem. Ich stimme zu, dass es zu schwer ist, in einem Interview zu lösen, aber das bedeutet nicht, dass es zu schwer ist, in einem Interview zu fragen. Der arme Kandidat wird keine Antwort haben, der durchschnittliche Kandidat wird die offensichtliche Antwort erraten und der gute Kandidat wird erklären, warum das Problem zu schwer zu beantworten ist.
Ich halte dies für eine offene Frage, die dem Interviewer einen Einblick in den Kandidaten gibt. Aus diesem Grund ist es eine gute Frage, die Sie während eines Interviews stellen sollten , auch wenn sie während eines Interviews zu schwer zu lösen sind . Eine Frage zu stellen ist mehr als nur zu prüfen, ob die Antwort richtig oder falsch ist.
quelle
Unten ist C-Code, um die Anzahl der Werte des 2N-Tupels von Indizes zu zählen, die Rand erzeugen und die Wahrscheinlichkeit berechnen kann. Beginnend mit N = 0 werden Zählungen von 1, 1, 8, 135, 4480, 189125 und 12450816 mit Wahrscheinlichkeiten von 1, 1, .5, .185185, .0683594, .0193664 und .00571983 angezeigt. Die Zählungen erscheinen nicht in der Encyclopedia of Integer Sequences , daher hat entweder mein Programm einen Fehler oder dies ist ein sehr dunkles Problem. In diesem Fall soll das Problem nicht von einem Bewerber gelöst werden, sondern einige seiner Denkprozesse und der Umgang mit Frustration aufdecken. Ich würde es nicht als gutes Interviewproblem ansehen.
quelle
Das Verhalten des Algorithmus kann als Markov-Kette über der symmetrischen Gruppe S N modelliert werden .
Grundlagen
Die N Elemente des Arrays
A
können in N angeordnet werden ! verschiedene Permutationen. Nummerieren wir diese Permutationen von 1 bis N !, ZB durch lexikografische Reihenfolge. Also der Zustand des ArraysA
zu jedem Zeitpunkt im Algorithmus vollständig durch die Permutationsnummer charakterisiert werden.Zum Beispiel für N = 3 eine mögliche Nummerierung aller 3! = 6 Permutationen können sein:
Zustandsübergangswahrscheinlichkeiten
In jedem Schritt des Algorithmus
A
bleibt der Zustand entweder gleich oder geht von einer dieser Permutationen zu einer anderen über. Wir sind jetzt an den Wahrscheinlichkeiten dieser Zustandsänderungen interessiert. Nennen wir Pr ( i → j ) die Wahrscheinlichkeit, dass sich der Zustand in einer einzelnen Schleifeniteration von Permutation i zu Permutation j ändert .Wenn wir m und n gleichmäßig und unabhängig vom Bereich [0, N -1] auswählen , gibt es N. mögliche Ergebnisse, von denen jedes gleich wahrscheinlich ist.
Identität
Für N dieser Ergebnisse gilt m = n , so dass sich die Permutation nicht ändert. Deshalb,
Transpositionen
Die verbleibenden N² - N Fälle sind Transpositionen, dh zwei Elemente tauschen ihre Positionen aus und daher ändert sich die Permutation. Angenommen, eine dieser Transpositionen tauscht die Elemente an den Positionen x und y aus . Es gibt zwei Fälle, in denen diese Transposition durch den Algorithmus erzeugt werden kann: entweder m = x , n = y oder m = y , n = x . Somit beträgt die Wahrscheinlichkeit für jede Transposition 2 / N² .
Wie hängt das mit unseren Permutationen zusammen? Nennen wir zwei Permutationen i und j Nachbarn, wenn und nur wenn es eine Transposition gibt, die i in j umwandelt (und umgekehrt). Wir können dann schließen:
Übergangsmatrix
Wir können die Wahrscheinlichkeiten Pr ( i → j ) in einer Übergangsmatrix P ∈ [0,1] N ! × N ! . Wir definieren
wobei p ij ist der Eintrag in der i -ten Zeile und j -ten Spalte von P . Beachten Sie, dass
was bedeutet, dass P symmetrisch ist.
Der entscheidende Punkt ist nun die Beobachtung dessen, was passiert, wenn wir P mit sich selbst multiplizieren . Nehmen jedes Element p (2) ij von P ²:
Das Produkt Pr ( i → k ) · Pr ( k → j ) ist die Wahrscheinlichkeit, dass wir ab der Permutation i in einem Schritt in die Permutation k und nach einem weiteren nachfolgenden Schritt in die Permutation j übergehen. Die Summierung aller dazwischen liegenden Permutationen k ergibt daher die Gesamtwahrscheinlichkeit des Übergangs von i nach j in 2 Schritten .
Dieses Argument kann auf höhere Potenzen von P ausgedehnt werden . Eine besondere Konsequenz ist folgendes:
Beispiel
Lassen Sie uns dies mit N = 3 durchspielen . Wir haben bereits eine Nummerierung für die Permutationen. Die entsprechende Übergangsmatrix lautet wie folgt:
Das Multiplizieren von P mit sich selbst ergibt:
Eine weitere Multiplikation ergibt:
Jedes Element der Hauptdiagonale gibt uns die gewünschte Wahrscheinlichkeit, das ist 15 / 81 oder 5 / 27 .
Diskussion
Während dieser Ansatz mathematisch fundiert ist und auf jeden Wert von N angewendet werden kann , ist er in dieser Form nicht sehr praktisch. Die Übergangsmatrix P hat N ! ²-Einträge, die sehr schnell riesig werden. Selbst für N = 10 überschreitet die Größe der Matrix bereits 13 Billionen Einträge. Eine naive Implementierung dieses Algorithmus erscheint daher nicht realisierbar.
Im Vergleich zu anderen Vorschlägen ist dieser Ansatz jedoch sehr strukturiert und erfordert keine komplexen Ableitungen, außer herauszufinden, welche Permutationen Nachbarn sind. Ich hoffe, dass diese Struktur genutzt werden kann, um eine viel einfachere Berechnung zu finden.
Zum Beispiel könnte man die Tatsache ausnutzen, dass alle diagonalen Elemente einer Potenz von P gleich sind. Angenommen, wir können die Spur von P N leicht berechnen , dann ist die Lösung einfach tr ( P N ) / N ! Die Spur von P N ist gleich der Summe der N- ten Potenzen seiner Eigenwerte. Wenn wir also einen effizienten Algorithmus zur Berechnung der Eigenwerte von P hätten , wären wir gesetzt. Ich habe dies jedoch nicht weiter untersucht, als die Eigenwerte bis zu N = 5 zu berechnen .
quelle
Es ist leicht, die Grenzen 1 / n n <= p <= 1 / n zu beobachten.
Hier ist eine unvollständige Idee, eine invers-exponentielle Obergrenze zu zeigen.
Sie zeichnen 2n mal Zahlen aus {1,2, .., n}. Wenn eines davon eindeutig ist (tritt genau einmal auf), wird das Array definitiv geändert, da das Element verschwunden ist und nicht mehr an seinen ursprünglichen Platz zurückkehren kann.
Die Wahrscheinlichkeit, dass eine feste Zahl eindeutig ist, beträgt 2n * 1 / n * (1-1 / n) ^ (2n-1) = 2 * (1-1 / n) ^ (2n-1), was asympotisch 2 / e ist 2 , begrenzt von 0. [2n, weil Sie wählen, bei welchem Versuch Sie es bekommen, 1 / n, dass Sie es bei diesem Versuch bekommen haben, (1-1 / n) ^ (2n-1), dass Sie es nicht bekommen haben andere Versuche]
Wenn die Ereignisse unabhängig wären, würden Sie die Chance bekommen, dass alle Zahlen nicht eindeutig sind (2 / e 2 ) ^ n, was p <= O ((2 / e 2 ) ^ n) bedeuten würde . Leider sind sie nicht unabhängig. Ich bin der Meinung, dass die Grenze mit einer differenzierteren Analyse gezeigt werden kann. Das Schlüsselwort lautet "Balls and Bins Problem".
quelle
Eine vereinfachende Lösung ist
Da ein möglicher Weg das Array gleich bleibt, ist wenn
m = n
für jede Iteration. Undm
gleichn
mit der Möglichkeit1 / N
.Es ist sicherlich höher als das. Die Frage ist, um wie viel ..
Zweiter Gedanke: Man könnte auch argumentieren, dass jede Permutation die gleiche Wahrscheinlichkeit hat, wenn Sie ein Array zufällig mischen. Da es
n!
Permutationen gibt, ist die Wahrscheinlichkeit, nur eine zu bekommen (die, die wir am Anfang haben), großDas ist ein bisschen besser als das vorherige Ergebnis.
Wie diskutiert, ist der Algorithmus voreingenommen. Dies bedeutet, dass nicht jede Permutation die gleiche Wahrscheinlichkeit hat. Ist
1 / N!
also nicht ganz genau. Sie müssen herausfinden, wie die Verteilung der Permutationen ist.quelle
n!
sich nicht immer teiltn^n
, betrachten Sie einfach den Fall, in demn
eine Primzahl größer als 2 ist.Zu Ihrer Information, ich bin mir nicht sicher, ob die obige Grenze (1 / n ^ 2) gilt:
Stichprobencode:
quelle
Jeder geht davon aus
A[i] == i
, was nicht ausdrücklich angegeben wurde. Ich werde diese Annahme auch machen, aber beachte, dass die Wahrscheinlichkeit vom Inhalt abhängt. Zum Beispiel wennA[i]=0
, dann ist die Wahrscheinlichkeit = 1 für alle N.Hier erfahren Sie, wie es geht. Sei
P(n,i)
die Wahrscheinlichkeit, dass sich das resultierende Array um genau i Transpositionen vom ursprünglichen Array unterscheidet.Wir wollen es wissen
P(n,0)
. Es ist wahr, dass:Erläuterung: Wir können das ursprüngliche Array auf zwei Arten erhalten, indem wir entweder eine "neutrale" Transposition in einem Array durchführen, das bereits gut ist, oder indem wir die einzige "schlechte" Transposition zurücksetzen. Um ein Array mit nur einer "schlechten" Transposition zu erhalten, können wir ein Array mit 0 schlechten Transpositionen nehmen und eine Transposition durchführen, die nicht neutral ist.
EDIT: -2 statt -1 in P (n-1,0)
quelle
A[i] == i
. 2) Ich glaube nicht, dass esP(n,i)
im Allgemeinen einen einfachen Weg gibt . Es ist leicht fürP(n,0)
, aber für größerei
ist unklar, wie viele Transpositionen "gut" und wie viele "schlecht" sind.P(n,0)
aber genau darum geht es in der Frage. Wenn Sie mit dieser Argumentation nicht einverstanden sind, geben Sie ein Beispiel an, wo sie fehlschlägt oder warum sie falsch ist.P(n-1,1) = (1-1/(n-1)) * P(n-2,0)
. Wenn Sie sich in der Mitte befinden, können Sie einen weiteren schlechten Schritt hinzufügen, den Sie später rückgängig machen werden. Betrachten Sie zum Beispiel (1234) => (2134) => (2143) => (1243) => (1234). Die Zahl n-1 im Nenner ist ebenfalls verdächtig, da die Zufallsfunktion eine Wiederholung ermöglicht.Es ist keine vollständige Lösung, aber es ist zumindest etwas.
Nehmen Sie einen bestimmten Satz von Swaps, die keine Wirkung haben. Wir wissen, dass es der Fall gewesen sein muss, dass seine Swaps eine Reihe von Loops unterschiedlicher Größe bildeten, wobei insgesamt
n
Swaps verwendet wurden. (Zu diesem Zweck kann ein Swap ohne Wirkung als Schleife der Größe 1 betrachtet werden.)Vielleicht können wir
1) Teilen Sie sie anhand der Größe der Schleifen in Gruppen auf
2) Berechnen Sie die Anzahl der Möglichkeiten, um jede Gruppe zu erhalten.
(Das Hauptproblem ist, dass es eine Menge verschiedener Gruppen gibt, aber ich bin mir nicht sicher, wie Sie dies tatsächlich berechnen würden, wenn Sie die verschiedenen Gruppierungen nicht berücksichtigen.)
quelle
Interessante Frage.
Ich denke, die Antwort ist 1 / N, aber ich habe keinen Beweis. Wenn ich einen Beweis finde, werde ich meine Antwort bearbeiten.
Was ich bis jetzt habe:
Wenn m == n, wird das Array nicht geändert. Die Wahrscheinlichkeit, m == n zu erhalten, beträgt 1 / N, da es N ^ 2 Optionen gibt und nur N für jede 0 <= i <= N-1 geeignet ist ((i, i)).
Somit erhalten wir N / N ^ 2 = 1 / N.
Bezeichne Pk die Wahrscheinlichkeit, dass nach k Iterationen von Swaps das Array der Größe N gleich bleibt.
P1 = 1 / N. (Wie wir unten gesehen haben)
P2 = (1 / N) P1 + (N-1 / N) (2 / N ^ 2) = 1 / N ^ 2 + 2 (N-1) / N ^ 3.
Pk = (1 / N) * Pk-1 + (N-1 / N) * X. (der erste für m == n, der zweite für m! = n)
Ich muss mehr darüber nachdenken, was X gleich ist. (X ist nur ein Ersatz für die reale Formel, keine Konstante oder irgendetwas anderes)
EDIT: Ich möchte einen anderen Ansatz vorstellen:
Wir können Swaps in drei Gruppen einteilen: konstruktive Swaps, destruktive Swaps und harmlose Swaps.
Konstruktiver Swap ist ein Swap, bei dem mindestens ein Element an die richtige Stelle verschoben wird.
Destruktiver Swap ist ein Swap, bei dem sich mindestens ein Element von seiner korrekten Position bewegt.
Harmloser Swap ist ein Swap, der nicht zu den anderen Gruppen gehört.
Es ist leicht zu erkennen, dass dies eine Partition aller möglichen Swaps ist. (Schnittpunkt = leere Menge).
Nun die Behauptung, die ich beweisen möchte:
Wenn jemand ein Gegenbeispiel hat, schreiben Sie es bitte als Kommentar auf.
Wenn diese Behauptung richtig ist, können wir alle Kombinationen nehmen und summieren - 0 harmlose Swaps, 1 harmlose Swaps, .., N harmlose Swaps.
Und für jeden möglichen k harmlosen Tausch prüfen wir, ob Nk gerade ist, wenn nein, überspringen wir. Wenn ja, nehmen wir (Nk) / 2 als destruktiv und (Nk) als konstruktiv. Und schauen Sie einfach alle Möglichkeiten.
quelle
Ich würde das Problem als Multigraph modellieren, bei dem Knoten Elemente des Arrays sind und Swaps eine ungerichtete (!) Verbindung zwischen ihnen hinzufügen. Dann suchen Sie irgendwie nach Schleifen (alle Knoten sind Teil einer Schleife => Original)
Ich muss wirklich wieder arbeiten! :(
quelle
Nun, aus mathematischer Sicht:
Damit die Array-Elemente jedes Mal an derselben Stelle ausgetauscht werden, muss die Rand (N) -Funktion zweimal dieselbe Zahl für int m und int n generieren. Die Wahrscheinlichkeit, dass die Rand (N) -Funktion zweimal dieselbe Zahl erzeugt, beträgt also 1 / N. und wir haben Rand (N) N-mal innerhalb der for-Schleife aufgerufen, also haben wir eine Wahrscheinlichkeit von 1 / (N ^ 2)
quelle
Naive Implementierung in C #. Die Idee ist, alle möglichen Permutationen des anfänglichen Arrays zu erstellen und sie aufzulisten. Dann bauen wir eine Matrix möglicher Zustandsänderungen auf. Wenn Sie die Matrix N-mal mit sich selbst multiplizieren, erhalten Sie die Matrix, die zeigt, wie viele Wege existieren, die in N Schritten von der Permutation #i zur Permutation #j führen. Elemet [0,0] zeigt, wie viele Wege zum gleichen Ausgangszustand führen. Die Summe der Elemente der Zeile 0 zeigt die Gesamtzahl der verschiedenen Möglichkeiten. Durch Teilen von ersteren zu letzteren erhalten wir die Wahrscheinlichkeit.
Tatsächlich beträgt die Gesamtzahl der Permutationen N ^ (2N).
quelle
Die Wahrscheinlichkeit, dass m == n bei jeder Iteration ist, dann mache das N-mal. P (m == n) = 1 / N. Ich denke also, dass P = 1 / (n ^ 2) für diesen Fall ist. Aber dann müssen Sie berücksichtigen, dass die Werte zurückgetauscht werden. Ich denke also, die Antwort ist (Texteditor hat mich) 1 / N ^ N.
quelle
(1/N)^N
. Die Sache ist, dass an sich die Wahrscheinlichkeit ist, dass sich das Array nie wirklich ändert. Wir haben immer noch nicht die Wahrscheinlichkeit gezählt, dass sich Dinge bewegen und einfach in den ursprünglichen Zustand zurückkehren.Frage: Wie groß ist die Wahrscheinlichkeit, dass Array A gleich bleibt? Bedingung: Angenommen, das Array enthält eindeutige Elemente.
Versuchte die Lösung in Java.
Das zufällige Austauschen erfolgt auf dem primitiven int-Array. In der Java-Methode werden Parameter immer als Wert übergeben, sodass das, was in der Swap-Methode geschieht, keine Rolle spielt, da [m] und a [n] Elemente des Arrays (von unten Code Swap (a [m], a [n])) sind nicht vollständiges Array übergeben.
Die Antwort lautet: Array bleibt gleich. Trotz des oben genannten Zustands. Siehe unten Java-Codebeispiel:
Beispielausgabe:
Füllarray: Druckarray: 3 1 1 4 9 7 9 5 9 5 Austauscharray: Druckarray: 3 1 1 4 9 7 9 5 9 5
quelle
swap