Mischen Sie die Elemente eines Arrays/n Zahlen gleichmäßig nach dem Zufallsprinzip. Möglicherweise in erwarteter O(n)-Zeit

Question

Ist es möglich, die Elemente eines Feldes der Größe n gleichmäßig zu mischen, d. h., die Wahrscheinlichkeit, dass jede der n! O(n) Zeit. Wie das? Ich muss die Elemente der A in ein neues Array B Das erste, was mir in den Sinn kommt, wenn ich versuche, dies zu tun, ist, eine zufällige Zahl zu wählen i von 1 bis n, um zu sehen, ob A[i] bereits ausgewählt wurde, wenn ja, dann wiederholen, ansonsten A[i] an der ersten freien Stelle in B . Dieses Problem des Couponsammelns hat jedoch einen erwarteten Zeitaufwand O(n log n) . Kann jemand einen Vorschlag für eine O(n) Algorithmus der erwarteten Zeit.

Danke.

Answer 1

Sie sollten sich die Fisher-Yates schlurfen.

Aus dem Artikel:

P Shuffle ist unvoreingenommen, so dass jeder Permutation gleich wahrscheinlich ist. Die moderne Version des Algorithmus ist auch recht effizient, da sie nur Zeit proportional zur Anzahl der zu mischenden Elemente und keinen zusätzlichen Speicherplatz.

Es entspricht also Ihren Anforderungen. Es ist auch ziemlich einfach zu implementieren.

Answer 2

Für jede Array-Position:

Auswahl einer Zufallszahl von der aktuellen Position bis zum Ende des Arrays

Aktuelle Position mit zufälliger Position vertauschen

Das sollte O(n) ergeben, ohne die Herausforderung, eine unbenutzte Array-Position zu finden. Dies setzt voraus, dass Sie einen In-Place-Swap verwenden können und dass Sie kein neues Array erstellen müssen.

Answer 3

Was Sie wollen, ist Stichprobe der Menge die jedes Element mit gleicher Wahrscheinlichkeit abfragt.