Vor einigen Monaten habe ich darüber gebloggt, eine zufällige Permutation einer Liste von ganzen Zahlen zu erhalten. Sie könnten das als eine Permutation von Indizes der Menge verwenden, die Ihre Elemente enthält, und dann haben Sie, was Sie wollen.
Im ersten Post erkunde ich einige Möglichkeiten, und schließlich bekomme ich "eine Funktion, um zufällig eine generische Liste mit O (n) Komplexität zu permutieren", richtig gekapselt, um an unveränderlichen Daten zu arbeiten (dh es ist frei von Nebenwirkungen) .
Im zweiten Beitrag mache ich es gleichmäßig verteilt.
Der Code ist in F #, ich hoffe es stört dich nicht!
Viel Glück.
BEARBEITEN: Ich habe keinen formalen Beweis, aber die Intuition sagt mir, dass die Komplexität eines solchen Algorithmus nicht niedriger sein kann als O (n) . Ich würde es wirklich schätzen, wenn es schneller erledigt wird!
Eine einfache Möglichkeit, die Reihenfolge zu randomisieren, besteht darin, eine neue Liste der richtigen Größe zu erstellen (20 in Ihrem Fall), über die erste Liste zu iterieren und jedes Element an einer zufälligen Position zur zweiten Liste hinzuzufügen. Wenn die zufällige Position bereits gefüllt ist, legen Sie sie in die nächste freie Position.
Ich denke, dieser Pseudocode ist korrekt:
%Vor%EDIT: also stellt sich heraus, dass diese Antwort eigentlich nicht so gut ist. Es ist weder besonders schnell, noch besonders zufällig. Vielen Dank für Ihre Kommentare. Für eine gute Antwort scrollen Sie bitte zurück zum Anfang der Seite: -)
Wahrscheinlich hat jemand bereits das Mischen für Sie implementiert. Zum Beispiel können Sie in Python random.shuffle in C ++ random_shuffle , und in PHP shuffle .