Wie kann ich eine Zufallszahl erzeugen, die im Bereich (1,n) ist, aber nicht in einer bestimmten Liste (i,j)?Generiere eine Zahl ist Bereich (1, n), aber nicht in einer Liste (i, j)
Beispiel: Bereich ist (1,500), Liste ist [1,3,4,45,199,212,344].
Hinweis: Die Liste nicht
sortiert werden könnenEine Methode ist die Ablehnung Probenahme:
x im Bereich (1, 500)x in deiner Liste der verbotenen Werte? (Kann ein Hash-Set für diese Prüfung verwendet werden.)
x ist Ihr Zufallswert, getanDies wird funktionieren Wenn Ihr Satz erlaubter Werte wesentlich größer ist als Ihr Satz unzulässiger Werte:
Wenn es G mögliche gute Werte und B mögliche schlechte Werte gibt, dann müssen Sie die zu erwartende Anzahl von Malen x aus derabfragenWerte, bis Sie einen guten Wert erhalten, ist (G + B)/G (die Erwartung der zugehörigen geometrischen Verteilung). (Sie können dies spüren überprüfen. Wie G bis ins Unendliche geht, die Erwartung geht auf 1. Wie B bis ins Unendliche geht, geht die Erwartung, bis ins Unendliche.)
Eine andere Methode, eine Liste zu machen ist L aller zulässigen Werte, dann Beispiel L[rand(L.count)].
Timothy hat beide richtige Standard Antworten aufgeführt. Die Zurückweisungsabtastung ist die normale Lösung, wenn der Bereich viel größer ist als die Liste der unzulässigen Werte (und unbequem im Speicher zu speichern). Die Methode zum Abtasten einer Liste ist optimal, wenn es einfach ist, die Liste zulässiger Werte im Speicher zu speichern. –
Ich nehme an, dass Sie wissen, wie man eine Zufallszahl in [1, n] erzeugt und auch Ihre Liste ist wie im obigen Beispiel angeordnet.
Nehmen wir an, Sie haben eine Liste mit k Elementen. Machen Sie eine Kartenstruktur (O (logn)), die Geschwindigkeit garantiert, wenn k höher geht. Setzen Sie alle Elemente aus der Liste in die Karte, wobei Elementwert der Schlüssel und "guter" Wert der Wert ist. Später werde ich über "guten" Wert erklären. Wenn wir also die Karte haben, dann finde einfach eine Zufallszahl in [1, n - k - p] (Später werde ich erklären, was p ist) und wenn diese Zahl in der Karte ist, dann ersetze sie durch "guten" Wert.
"GOOD" -Wert -> Beginnen wir mit dem k-ten Element. Es ist ein guter Wert ist sein eigener Wert + 1, denn das nächste Element ist "gut" für uns. Nun schauen wir uns das (k-1) -te Element an. Wir nehmen an, dass sein guter Wert wieder sein eigener Wert + 1 ist. Wenn dieser Wert gleich dem k-ten Element ist, dann ist der "gute" Wert für das (k-1) -te Element der k-te "gute" Wert +1 Sie müssen den größten "guten" Wert speichern. Wenn der größte Wert größer als n ist, dann ist p (von oben) p = am größten - n.
Natürlich empfehle ich dir das nur, wenn k eine große Zahl ist, sonst ist @Timothy Shields Methode perfekt.
Die Technik, die ich in der Regel verwendet werden, wenn die Liste Länge 1 ist eine zufällige ganze Zahl r in [1,n-1] zu erzeugen, und wenn r größer oder gleich ist, dann auf diesen einzigen illegal Wert r inkrementieren.
Dies kann für eine Liste der Länge k für kleine k verallgemeinert werden, sondern erfordert diese Liste Sortierung (Sie können Ihre Vergleichs- und Schritt in zufälliger Reihenfolge nicht tun). Wenn die Liste mäßig lang ist, können Sie nach der Sortierung mit einer bsearch beginnen und die Anzahl der übersprungenen Werte zu r hinzufügen und dann in den Rest der Liste rekursiv gehen.
Eine Liste der Länge k, kein Wert, der größer oder gleich n-k enthalten, Sie kann eine direkte Substitution tun: erzeugen zufällige r in [1,n-k] und dann durch die Liste Tests durchlaufen, wenn r zu list[i] gleich ist. Wenn es ist, dann setzen Sie r auf n-k+i (dies setzt voraus, list ist Null-basierte) und beenden. Dieser zweite Ansatz schlägt fehl, wenn sich einige der Listenelemente in [n-k,n] befinden.
Ich könnte versuchen, etwas Gescheites zu diesem Zeitpunkt zu investieren, aber was ich bisher für eine gleichmäßige Verteilung mit Werten von k ausreichend scheint viel weniger als n ...
n-k, und der andere der Rest (dies kann vor Ort getan werden).r in [1,n-k]r ist list[i] eingestellt dann r zu n-k+i und gehen Sie zu Schritt 5).r in Schritt 3 nicht geändert wurde, dann sind wir fertig.Beobachtungen:
r in den Gefahrenbereich zu fahren.k Ansätze n nähert, wächst die maximale Größe der oberen (sortierten) Liste.k, wenn mehr Wert in der oberen Liste erscheint (je größer die Sortierung), die Chance, einen Treffer in der unteren Liste zu erhalten, schrumpft, die Wahrscheinlichkeit der Notwendigkeit, die Sortierung zu tun.Refinement: Offensichtlich Dinge sehr Sorty für große k, aber in solchen Fällen die Liste hat vergleichsweise wenige Löcher, in die r erlaubt ist, zu begleichen. Dies könnte sicherlich ausgenutzt werden.
Ich könnte etwas anderes vorschlagen, wenn viele zufällige Werte mit der gleichen Liste und Grenzen benötigt wurden. Ich hoffe, dass die Liste der ungültigen Werte nicht die Liste der Ergebnisse der vorherigen Aufrufe an diese Funktion ist, denn wenn Sie dann möchten, dann möchten Sie nichts davon - stattdessen würden Sie eine Fisher-Yates Shuffle wollen.
Ablehnungs-Sampling wäre am einfachsten, wie bereits beschrieben. Wenn Sie dies jedoch nicht verwenden möchten, können Sie den Bereich und die unzulässigen Werte in Sets umwandeln und den Unterschied finden. Dann könnten Sie einen zufälligen Wert von dort wählen.
Angenommen, Sie wollten, dass der Bereich in [1, n] ist, aber nicht in [i, j], und Sie wollten, dass sie gleichmäßig verteilt sind.
In Python
total = range(1,n+1)
disallowed = range(i,j+1)
allowed = list(set(total) - set(disallowed))
return allowed[random.randrange(len(allowed))]
(Beachten Sie, dass diese Uniform da in alle Wahrscheinlichkeit nicht genau ist, max_rand%len(allowed) != 0 aber dies wird in den meisten praktischen Anwendungen sehr nahe)
Ich nehme an, Sie wollen, dass es stattdessen effizient sein nur Zahlen zu generieren, bis es nicht in deiner Liste ist? –
"Die Liste ist möglicherweise nicht sortiert" - Ich lese das "wird unsortiert dargestellt" statt "Sie können die Liste nicht sortieren". Es kann hilfreich sein, mögliche Implementierungssprachen anzugeben. Python und C++ haben Funktionen definiert, die nützlich sind, zum Beispiel – Spaceghost
Wenn n klein ist, können Sie eine Liste von Elementen erstellen, für Ihr Beispiel wäre das Array {2,5,6,7.444,66, .. 500 } (Sie erhalten den Punkt) und generieren Sie dann einfach einen zufälligen Index wie rand (493) in Ihrem Beispiel. und nimm das Element aus dem Array [rand (493)]. – Mark