Gibt es einen Algorithmus, der bei gegebener Liste von Symbolen {a1, a2, a3, ..., ak} in O (n) Zeit eine neue Liste der gleichen Symbole in a erzeugt zufällige Reihenfolge ohne Verzerrung? "Ohne Fehler" bedeutet die Wahrscheinlichkeit, dass irgendein Symbol s in einer Position p in der Liste ist 1/k endet.Zufälliges Sortieren eines Arrays
Angenommen, es ist möglich, eine ungerichtete Ganzzahl von 1-k inklusive in O (1) -Zeit zu erzeugen. Man nehme auch an, dass O (1) -Elementzugriff/-mutation möglich ist, und dass es möglich ist, eine neue Liste der Größe k in O (k) -Zeit zu erstellen.
Insbesondere wäre ich an einem generativen Algorithmus interessiert. Das heißt, ich wäre an einem Algorithmus interessiert, der O (1) initialen Overhead hat und dann ein neues Element für jeden Slot in der Liste erzeugt, wobei O (1) Zeit pro Slot genommen wird.
Wenn keine Lösung für das Problem besteht, wie beschrieben, möchte ich noch über Lösungen wissen, das nicht meine Zwänge in einer oder mehreren der folgenden Arten (und/oder auf andere Weise, falls erforderlich) erfüllen:
- die Zeit Komplexität ist schlechter als O (n).
- der Algorithmus ist in Bezug auf die endgültigen Positionen der Symbole voreingenommen.
- der Algorithmus ist nicht generativ.
Ich sollte hinzufügen, dass dieses Problem das gleiche wie das Problem der zufällig Sortieren der ganzen Zahlen von 1-k zu sein scheint, da wir die Liste der ganzen Zahlen von 1-k und dann für jede i integer sortieren In der neuen Liste können wir das Symbol ai erzeugen.
Welche Shuffle-Algorithmen haben Sie bisher berücksichtigt? Haben Sie sie aus bestimmten Gründen ausgeschlossen? –
@Greg: Ich hatte nichts wirklich Nützliches gefunden, aber ich habe anscheinend mit den falschen Stichwörtern gesucht (zufällige Sortierung, zufällige Sortierung ...). Die Suche nach "randomisierten Permutationen" und "Mischen" liefert mehr Ergebnisse. Ich habe jedoch noch nichts Generatives gefunden. – Cam
der Knuth Shuffle * ist generativ, entsprechend Ihrer Definition dieses Begriffs. –