Welche Verteilung erhalten Sie von diesem kaputten zufälligen Shuffle?

73

Der berühmte Fisher-Yates-Shuffle-Algorithmus kann verwendet werden, um ein Array A der Länge N zufällig zu permutieren:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

Ein häufiger Fehler, von dem mir immer wieder gesagt wurde, dass ich ihn nicht machen soll, ist folgender:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

Das heißt, anstatt eine zufällige Ganzzahl von k bis N auszuwählen, wählen Sie eine zufällige Ganzzahl von 1 bis N.

Was passiert, wenn Sie diesen Fehler machen? Ich weiß, dass die resultierende Permutation nicht gleichmäßig verteilt ist, aber ich weiß nicht, welche Garantien es für die resultierende Verteilung gibt. Hat jemand einen Ausdruck für die Wahrscheinlichkeitsverteilungen über die Endpositionen der Elemente?

templatetypedef
quelle
1
Möchten Sie wirklich 1-basierte Indizes?
Svante
Das kommt mir bekannt vor. Wurde dies in den letzten zwei Monaten auf SO diskutiert oder auf Programmierern?
Oosterwal
@ oosterwal- Ich habe diese Frage vor ungefähr drei Wochen gestellt und keine gute Antwort erhalten. Deshalb habe ich eine große Prämie darauf gesetzt, um das Interesse daran zu wecken. Hoffentlich kann jemand uns alle aufklären!
Templatetypedef
Ich habe (noch) keine Antwort, aber eine Sache, die mir aufgefallen ist, ist, dass sich jede Karte höchstwahrscheinlich an der Position befindet, hinter der sie begonnen hat. Außerdem sind sowohl die erste Karte als auch die letzte Position gleichmäßig verteilt - das heißt, die erste Karte hat die gleiche Wahrscheinlichkeit, an einer beliebigen Position zu landen, und jede Karte hat die gleiche Wahrscheinlichkeit, an der letzten Position zu landen. Jede richtige Lösung muss diese Eigenschaften aufweisen.
BlueRaja - Danny Pflughoeft
1
@Svante: warum nicht? Viele Sprachen, beginnend mit Pascal, das häufig zur Beschreibung von Algorithmen verwendet wurde, einschließlich Lua, haben Indizes, die bei 1 beginnen. IIRC, Pascal erlaubt das Starten von Array-Indizes bei einer beliebigen Anzahl, standardmäßig jedoch bei 1.
PhiLho

Antworten:

55

Ein empirischer Ansatz.

Lassen Sie uns den fehlerhaften Algorithmus in Mathematica implementieren:

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

Ermitteln Sie nun, wie oft sich jede Ganzzahl an jeder Position befindet:

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

Nehmen wir drei Positionen in den resultierenden Arrays und zeichnen die Häufigkeitsverteilung für jede Ganzzahl an dieser Position:

Für Position 1 lautet die Frequenzverteilung:

Geben Sie hier die Bildbeschreibung ein

Für Position 5 (Mitte)

Geben Sie hier die Bildbeschreibung ein

Und für Position 10 (letzte):

Geben Sie hier die Bildbeschreibung ein

und hier haben Sie die Verteilung für alle Positionen zusammen geplottet:

Geben Sie hier die Bildbeschreibung ein

Hier haben Sie eine bessere Statistik über 8 Positionen:

Geben Sie hier die Bildbeschreibung ein

Einige Beobachtungen:

  • Für alle Positionen ist die Wahrscheinlichkeit von "1" gleich (1 / n).
  • Die Wahrscheinlichkeitsmatrix ist symmetrisch in Bezug auf die große Antidiagonale
  • Die Wahrscheinlichkeit für eine beliebige Zahl an der letzten Position ist also ebenfalls einheitlich (1 / n).

Sie können diese Eigenschaften visualisieren, indem Sie den Anfang aller Linien vom selben Punkt (erste Eigenschaft) und der letzten horizontalen Linie (dritte Eigenschaft) betrachten.

Die zweite Eigenschaft ist aus dem folgenden Beispiel für eine Matrixdarstellung ersichtlich, in der die Zeilen die Positionen, die Spalten die Insassenzahl und die Farbe die experimentelle Wahrscheinlichkeit darstellen:

Geben Sie hier die Bildbeschreibung ein

Für eine 100x100-Matrix:

Geben Sie hier die Bildbeschreibung ein

Bearbeiten

Nur zum Spaß habe ich die genaue Formel für das zweite diagonale Element berechnet (das erste ist 1 / n). Der Rest kann erledigt werden, aber es ist viel Arbeit.

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

Verifizierte Werte von n = 3 bis 6 ({8/27, 57/256, 564/3125, 7105/46656})

Bearbeiten

Wenn wir die allgemeine explizite Berechnung in der Antwort von @wnoise ein wenig ausarbeiten, können wir ein wenig mehr Informationen erhalten.

Wenn wir 1 / n durch p [n] ersetzen, damit die Berechnungen nicht bewertet werden, erhalten wir beispielsweise für den ersten Teil der Matrix n = 7 (klicken, um ein größeres Bild zu sehen):

Geben Sie hier die Bildbeschreibung ein

Nachdem wir mit den Ergebnissen für andere Werte von n verglichen haben, können wir einige bekannte ganzzahlige Sequenzen in der Matrix identifizieren:

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

Sie können diese Sequenzen (in einigen Fällen mit unterschiedlichen Zeichen) in der wunderbaren http://oeis.org/ finden.

Das allgemeine Problem zu lösen ist schwieriger, aber ich hoffe, dies ist ein Anfang

Dr. Belisarius
quelle
29

Der "häufige Fehler", den Sie erwähnen, ist das Mischen durch zufällige Transpositionen. Dieses Problem wurde von Diaconis und Shahshahani bei der Erzeugung einer zufälligen Permutation mit zufälligen Transpositionen (1981) ausführlich untersucht . Sie führen eine vollständige Analyse der Stoppzeiten und der Konvergenz zur Gleichmäßigkeit durch. Wenn Sie keinen Link zum Papier erhalten, senden Sie mir bitte eine E-Mail und ich kann Ihnen eine Kopie weiterleiten. Es macht wirklich Spaß zu lesen (wie die meisten Artikel von Persi Diaconis).

Wenn das Array wiederholte Einträge hat, ist das Problem etwas anders. Als schamloser Plug wird dieses allgemeinere Problem von mir, Diaconis und Soundararajan in Anhang B einer Faustregel für das Mischen von Riffeln (2011) angesprochen .

PengOne
quelle
1
Befasst sich das Papier von 1981 tatsächlich mit dieser besonderen Situation? Ich dachte, das Problem als Zustand sei die Verteilung der Permutationen der Form (1 a_1) (2 a_2) ... (n a_n), wobei jedes a_i einheitlich aus 1..n ausgewählt wird.
mhum
1
@mhum: Ich glaube du hast recht, dass es nicht ganz so ist. Obwohl ich keinen unmittelbaren Zugang zu dem Papier von 1981 habe, decken die entsprechenden Ergebnisse in "Gruppendarstellungen in Wahrscheinlichkeit und Statistik" einheitlich zufällige Transpositionen ab, nicht diejenigen, bei denen die Transpositionen feste Elemente beinhalten. (Sie verallgemeinern sich gut, um gleichmäßig zufällig über jede Konjugationsklasse zu sein, aber ich kann nicht sehen, wie ich sie dazu bringen kann, sich hier direkt zu bewerben.)
wnoise
1
Es ist bedauerlich, dass dies die automatische Prämie bekam, da es die Frage nicht wirklich beantwortet ...
BlueRaja - Danny Pflughoeft
1
Ich weiß nicht, wie es war, wenn man bedenkt, dass Belisarius eine (zu Recht) höher bewertete Antwort hatte.
PengOne
1
@Peng Weil ich meine Antwort gepostet habe, bevor das Kopfgeld gestartet wurde
Dr. belisarius
15

Sagen wir

  • a = 1/N
  • b = 1-a
  • B i (k) ist die Wahrscheinlichkeitsmatrix nach iSwaps für das kth-Element. dh die Antwort auf die Frage "Wo ist knach iSwaps?". Zum Beispiel B 0 (3) = (0 0 1 0 ... 0)und B 1 (3) = (a 0 b 0 ... 0). Was Sie wollen, ist B N (k) für jedes k.
  • K i ist eine NxN-Matrix mit 1s in der i-ten Spalte und der i-ten Zeile, überall Nullen, z.

kappa_2

  • I i ist die Identitätsmatrix, aber mit dem Element x = y = i auf Null. ZB für i = 2:

I_2

  • A i ist

Ai = bIi + aKi

Dann,

B_n

Da jedoch B N (k = 1..N) die Identitätsmatrix bildet, ist die Wahrscheinlichkeit, dass sich ein gegebenes Element i am Ende an Position j befindet, durch das Matrixelement (i, j) der Matrix gegeben:

Lösungsmatrix

Zum Beispiel für N = 4:

B_4

Als Diagramm für N = 500 (Farbstufen sind 100 * Wahrscheinlichkeit):

B_500

Das Muster ist für alle N> 2 gleich:

  • Die wahrscheinlichste Endposition für das k-te Element ist k-1 .
  • Die am wenigsten wahrscheinliche Endposition ist k für k <N * ln (2) , sonst Position 1
Eelvex
quelle
Es ist einfach, Analyseergebnisse selbst für große Ns zu berechnen, aber die Ausdrücke sind zu "chaotisch", um sie hier aufzunehmen.
Eelvex
Das scheint richtig zu sein, aber ... wie bist du darauf gekommen? Ist das dasselbe wie die Antwort von wnoise ? (Entschuldigung, ich fürchte, ich verstehe stochastische Matrizen nicht.)
BlueRaja - Danny Pflughoeft
1
@EElvex Ich würde wissen, wie Sie das berechnet haben.
Mike Bailey
13

Ich wusste, dass ich diese Frage schon einmal gesehen hatte ...

" Warum führt dieser einfache Shuffle-Algorithmus zu voreingenommenen Ergebnissen? Was ist ein einfacher Grund? " Die Antworten enthalten viele gute Informationen, insbesondere einen Link zu einem Blog von Jeff Atwood über Coding Horror .

Wie Sie vielleicht bereits erraten haben, hängt die genaue Verteilung basierend auf der Antwort von @belisarius stark von der Anzahl der zu mischenden Elemente ab. Hier ist Atwoods Handlung für ein 6-Elemente-Deck:

Geben Sie hier die Bildbeschreibung ein

oosterwal
quelle
Vielen Dank für den Link / das Bild, aber alles, was dies bestätigt, ist, dass Sie etwas Uneinheitliches bekommen. Ich hoffte jedoch mehr auf eine analytische Lösung für die tatsächliche Verteilung.
Templatetypedef
1
Upvoted für das Teilen des Jeff Atwood-Links, der auch eine Möglichkeit zum Ableiten der Verteilung beschreibt - das unterbrochene Shuffle hat n ^ n gleich wahrscheinlich eine Auswahl an Zufallszahlen, die n zugeordnet sind! Ausgänge. Ich glaube nicht, dass Sie eine analytische Lösung bekommen werden. nur eine numerische für kleine Werte von n.
Chris Nash
9

Was für eine schöne Frage! Ich wünschte ich hätte eine vollständige Antwort.

Fisher-Yates ist schön zu analysieren, denn sobald es sich für das erste Element entscheidet, lässt es es in Ruhe. Der Voreingenommene kann ein Element wiederholt an jedem Ort ein- und auswechseln.

Wir können dies genauso analysieren wie eine Markov-Kette, indem wir die Aktionen als stochastische Übergangsmatrizen beschreiben, die linear auf Wahrscheinlichkeitsverteilungen wirken. Die meisten Elemente werden alleine gelassen, die Diagonale beträgt normalerweise (n-1) / n. Wenn sie bei Pass k nicht alleine gelassen werden, werden sie mit Element k (oder einem zufälligen Element, wenn sie Element k sind) getauscht. Dies ist 1 / (n-1) in Zeile oder Spalte k. Das Element in Zeile und Spalte k ist ebenfalls 1 / (n-1). Es ist einfach genug, diese Matrizen für k von 1 bis n zu multiplizieren.

Wir wissen, dass das Element an der letzten Stelle wahrscheinlich gleich irgendwo war, da der letzte Durchgang die letzte Stelle gleich wahrscheinlich mit einem anderen tauscht. In ähnlicher Weise wird das erste Element wahrscheinlich überall platziert. Diese Symmetrie ist darauf zurückzuführen, dass die Transponierte die Reihenfolge der Matrixmultiplikation umkehrt. Tatsächlich ist die Matrix in dem Sinne symmetrisch, dass Zeile i dieselbe wie Spalte (n + 1 - i) ist. Darüber hinaus zeigen die Zahlen nicht viel offensichtliches Muster. Diese genauen Lösungen stimmen mit den von belisarius durchgeführten Simulationen überein: In Slot i nimmt die Wahrscheinlichkeit ab, j zu erhalten, wenn j auf i steigt, seinen niedrigsten Wert bei i-1 erreicht und dann bei i auf seinen höchsten Wert springt abnehmend bis j n erreicht.

In Mathematica habe ich jeden Schritt mit generiert

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(Ich habe es nirgendwo dokumentiert gefunden, aber die erste Übereinstimmungsregel wird verwendet.) Die endgültige Übergangsmatrix kann berechnet werden mit:

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot ist ein nützliches Visualisierungswerkzeug.

Bearbeiten (von belisarius)

Nur eine Bestätigung. Der folgende Code enthält dieselbe Matrix wie in der Antwort von @ Eelvex:

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm
wnoise
quelle
1
Klingt interessant , aber ich habe nicht das bekommen , was Ihre Wahrscheinlichkeitsverteilungen sind auf - mir scheint , dass jeder Staat in der Markov - Kette sind Sie Bedarf die angeben , die Reihenfolge der gesamten n Elemente zu beschreiben (dh ein n-Element Problem erfordert ein (n!) - Markov-Kette angeben). Meinst Du das? Sie sind sich auch nicht sicher, ob das letzte Element wahrscheinlich von irgendwoher stammt - das ist der Fall, wenn alle n Elemente nach der Verarbeitung der ersten n-1 Elemente gleichmäßig zufällig verteilt sind, und ich glaube nicht, dass dies das ist Fall (oder zumindest möchte ich einen Beweis sehen).
j_random_hacker
Die Zustände sind die n Schlitze. Eintrag i, j in einer Übergangsmatrix ist die Chance, von Steckplatz i zu Steckplatz j zu gelangen. Wenn Sie eine Übergangsmatrix in eine Verteilung auf "wo Element ich gelandet bin" verwandeln, wählen Sie einfach Zeile i aus. Die Verteilung für "woher Element j kam" wählt nur Spalte j aus. Dies zählt in der Tat nicht für die Permutationen, sondern nur dafür, wo Elemente landen.
wnoise
1
@j_random_hacker: Die letzte Operation tauscht das letzte Element mit gleicher Wahrscheinlichkeit gegen ein Element aus. Unabhängig von der vorherigen Verteilung wird das letzte Element zufällig aus allen ausgewählt.
wnoise
Danke, nachdem ich etwas Algebra gemacht habe, verstehe ich jetzt Ihren letzten Punkt. In Bezug auf die Markov-Zustände: Sie meinen also, Sie verfolgen die Bewegung (= Wahrscheinlichkeiten, in jedem Slot zu sein) eines bestimmten Elements? (Angenommen, anfangs war das i-te Element i. Dann könnten wir sagen, dass die Spaltenvektortransponierung ([0, 0, 1, 0, ..., 0]) die anfängliche Wahrscheinlichkeitsverteilung des Ortes von Element 3 darstellt, und das Eine Vormultiplikation mit der Übergangsmatrix, die dem 1. Swap entspricht, würde die Wahrscheinlichkeitsverteilung der Position von Element 3 nach diesem Schritt ergeben ...
j_random_hacker
1
Ah gut. Ich war auf halbem Weg, einen weiteren Kommentar zu schreiben, aber ich glaube, ich bin jetzt auf der richtigen Seite. Grundsätzlich ist das Mischen gleichmäßig zufällig, wenn für jedes Element i das Ergebnis der Multiplikation der n Übergangsmatrizen, gefolgt von einem Spaltenvektor mit 1 in Zeile i und 0 an anderer Stelle gleich [1 / n, 1 / n, ..., 1 ist / n]. Dies entspricht der Anforderung, dass jede Spalte im Produkt der Übergangsmatrizen der Spalte entspricht, was der Anforderung entspricht, dass jeder einzelne Eintrag in der Produktmatrix 1 / n beträgt.
j_random_hacker
3

Die Wikipedia-Seite zum Fisher-Yates-Shuffle enthält eine Beschreibung und ein Beispiel dafür, was genau in diesem Fall passieren wird.

Jeremiah Willcock
quelle
2
Vielen Dank für den Link, aber ein Teil des Grundes, warum ich diese Frage gestellt habe, ist, dass der Wikipedia-Artikel nur besagt, dass Sie keine gleichmäßige Verteilung erhalten werden, nicht wie diese ungleichmäßige Verteilung mathematisch aussieht. Das heißt, es gibt keine Diskussion über die Wahrscheinlichkeit, dass ein bestimmtes Element an einem bestimmten Ort landet.
Templatetypedef
@templatetypedef: Es gibt eine Zahl dafür für einen einfachen Fall (ich glaube 6 oder 7 Elemente). Ich weiß jedoch, dass dies keine ganz allgemeine Antwort ist.
Jeremiah Willcock
3

Sie können die Verteilung mit stochastischen Matrizen berechnen . Die Matrix A (i, j) beschreibe die Wahrscheinlichkeit, dass die Karte ursprünglich an Position i an Position j endet. Dann hat der k-te Swap eine Matrix Ak, die durch Ak(i,j) = 1/Nif i == koder gegeben j == kist (die Karte in Position k kann überall landen und jede Karte kann mit gleicher Wahrscheinlichkeit an Position k landen), Ak(i,i) = (N - 1)/Nfür alle i != k(jede andere Karte bleibt an derselben Stelle mit Wahrscheinlichkeit (N-1) / N) und alle anderen Elemente Null.

Das Ergebnis des vollständigen Mischens ergibt sich dann aus dem Produkt der Matrizen AN ... A1.

Ich gehe davon aus, dass Sie nach einer algebraischen Beschreibung der Wahrscheinlichkeiten suchen. Sie können eines erhalten, indem Sie das obige Matrixprodukt erweitern, aber ich kann mir vorstellen, dass es ziemlich komplex sein wird!

UPDATE: Ich habe gerade die entsprechende Antwort von wnoise oben gesehen! Hoppla...

daoudc
quelle
3

Ich habe mich weiter damit befasst und es stellt sich heraus, dass diese Verteilung ausführlich untersucht wurde. Der Grund, warum es von Interesse ist, ist, dass dieser "kaputte" Algorithmus im RSA-Chip-System verwendet wird (oder wurde).

Elchanan Mossel, Yuval Peres und Alistair Sinclair untersuchen in Shuffling by semi-random transpositions dies und eine allgemeinere Klasse von Shuffles. Das Ergebnis dieses Papiers scheint zu sein, dass es log(n)unterbrochene Mischvorgänge erfordert, um eine nahezu zufällige Verteilung zu erreichen.

In The Bias of Three Pseudorandom Shuffles ( Aequationes Mathematicae , 22, 1981, 268-292) analysieren Ethan Bolker und David Robbins dieses Shuffle und stellen fest, dass der gesamte Variationsabstand zur Gleichmäßigkeit nach einem einzelnen Durchgang 1 beträgt, was darauf hinweist, dass es nicht sehr ist überhaupt zufällig. Sie geben auch asympotische Analysen.

Schließlich fanden Laurent Saloff-Coste und Jessica Zuniga eine schöne Obergrenze in ihrer Untersuchung inhomogener Markov-Ketten.

PengOne
quelle
2

Diese Frage bittet um eine interaktive visuelle Matrixdiagrammanalyse des erwähnten gebrochenen Shuffle. Ein solches Tool finden Sie auf der Seite Wird es mischen? - Warum zufällige Komparatoren von Mike Bostock schlecht sind .

Bostock hat ein hervorragendes Tool zur Analyse von Zufallskomparatoren zusammengestellt. Wählen Sie in der Dropdown-Liste auf dieser Seite einen naiven Austausch (zufällig ↦ zufällig) , um den fehlerhaften Algorithmus und das von ihm erzeugte Muster anzuzeigen .

Seine Seite ist informativ, da man sehen kann, welche unmittelbaren Auswirkungen eine Änderung der Logik auf die gemischten Daten hat. Zum Beispiel:

Dieses Matrixdiagramm mit einem ungleichmäßigen und sehr voreingenommenen Shuffle wird mit einem naiven Swap (wir wählen von "1 bis N") mit folgendem Code erstellt:

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

voreingenommenes Mischen

Wenn wir jedoch ein nicht voreingenommenes Shuffle implementieren, bei dem wir zwischen "k und N" wählen, sollten wir ein Diagramm wie das folgende sehen:

Geben Sie hier die Bildbeschreibung ein

wobei die Verteilung einheitlich ist und aus Code wie dem folgenden erstellt wird:

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}
Mac
quelle
Dies wäre eine viel bessere Antwort, wenn Sie hier weitere Informationen einfügen und diese nicht hinter einem Link verstecken würden.
Teepeemm
Ich stimme dir nicht zu. Ich sah keine Notwendigkeit zu versuchen, die ausgezeichneten Antworten zu wiederholen, die bereits von daoudc , wnoise , Eelvex und insbesondere belisarius gegeben wurden . In den Antworten auf dieser Seite fehlte lediglich eine Art interaktives Modell. Der Link bietet es.
Mac
1

Die hervorragenden Antworten, die bisher gegeben wurden, konzentrieren sich auf die Verteilung, aber Sie haben auch gefragt: "Was passiert, wenn Sie diesen Fehler machen?" - was ich noch nicht beantwortet habe, deshalb werde ich eine Erklärung dazu geben:

Der Knuth-Fisher-Yates-Shuffle-Algorithmus wählt 1 von n Elementen aus, dann 1 von n-1 verbleibenden Elementen und so weiter.

Sie können es mit zwei Arrays a1 und a2 implementieren , wo Sie ein Element aus a1 entfernen und in a2 einzufügen, aber der Algorithmus tut es an Ort und Stelle (was bedeutet, dass es nur ein Array benötigt), wie erklärt sich hier (Google: " Mischalgorithmen Fisher-Yates DataGenetics ") sehr gut.

Wenn Sie die Elemente nicht entfernen, können sie erneut zufällig ausgewählt werden, wodurch die voreingenommene Zufälligkeit entsteht. Dies ist genau das, was das zweite Beispiel, das Sie beschreiben, bewirkt. Das erste Beispiel, der Knuth-Fisher-Yates-Algorithmus, verwendet eine Cursor-Variable von k bis N, die sich merkt, welche Elemente bereits aufgenommen wurden, und daher vermeidet, Elemente mehr als einmal auszuwählen.

Matt
quelle
Denkst du, du könntest das "Hier" durch etwas googelbareres ersetzen?
Wolf
Fertig, ich habe einen Google-Suchhinweis hinzugefügt - "hier" war jedoch bereits ein Link.
Matt
Das ist das Problem mit hier verbindet: die Absicht des Schriftstellers offensichtlich sein, aber nicht für den Leser (bevor es folgende). Es ist, als würde man in eine Landschaft zeigen und sagen, schau dort hin! Das Problem ist, dass manchmal Webseiten verschwinden oder ganze Websites geschlossen werden (hoffentlich vorher archiviert): In dieser Zeit wird ein einfaches hier sinnlos. Trotzdem vielen Dank, dass Sie meinen Vorschlag berücksichtigt haben.
Wolf
@ Wolf: Guter Punkt, darüber habe ich vorher nicht nachgedacht. Sie haben Recht, wenn sich der Inhalt verschiebt, kann die Google-Suche dennoch hilfreich sein. Vielen Dank, dass Sie mich darauf aufmerksam gemacht haben!
Matt