2010-07-29 12 views
6

Ich bin gespannt, wie die beste Möglichkeit, eine zufällige Ganzzahl R, nicht in einer bereitgestellten Menge von ganzen Zahlen (R∉N) zu generieren. Ich kann mir verschiedene Möglichkeiten vorstellen, aber ich frage mich, was Sie alle denken.Optimal Algorithmus zum Generieren einer Zufallszahl R nicht in einer Reihe von Zahlen N

+1

Es hängt davon ab, wie diskret Ihre Sets sind. Was ist mehr wie das, was Sie wollen ?: (1) Generieren Sie eine zufällige Ganzzahl zwischen 1 und 50, aber nicht 4,5 oder 6 oder (2) Generieren Sie ein zufälliges Doppelt zwischen 0,0 und 1,0, aber nicht zwischen 0,1 und 0,2 – Justin

+0

I Tut mir leid, das habe ich nicht geklärt. R ist eine ganze Zahl und jede Zahl in N ist eine ganze Zahl. – Alan

Antwort

12

N sei die Größe der Gesamtmenge, und sei K die Größe der ausgeschlossenen Menge.

Ich hängt von der Größe des Satzes ab, von dem Sie abtasten. Wenn die ausgeschlossene Menge viel kleiner als der Gesamtbereich ist, wählen Sie einfach eine Zufallszahl, und wenn sie in der ausgeschlossenen Menge ist, wählen Sie erneut. Wenn wir den ausgeschlossenen Satz in einer Hash-Tabelle behalten, kann jeder Versuch in O (1) -Zeit durchgeführt werden.

Wenn die ausgeschlossene Menge groß ist, wählen Sie eine Zufallszahl R in einer Menge (N - K) und geben Sie die Auswahl als Element der nicht ausgeschlossenen Elemente aus. Wenn wir nur die Löcher in einer Hash-Tabelle speichern, die mit dem Wert der Zufallszahl verknüpft sind, können wir dies in einer Stichprobe in Zeit O (1) erzeugen.

Der Cutoff-Punkt wird von der Größe von (N - K)/N abhängen, aber ich vermute, dass, wenn dies größer als 0,5 oder so ist, oder Sie sind sehr klein, nur Proben bis Sie einen Treffer bekommen in der Praxis schneller sein.

+0

+1 - zeigten sowohl die selektiven als auch die restriktiven Fälle. – aperkins

+0

wow sehr gute Lösungen – Alan

+0

Gute Antwort im Prinzip, aber ich würde nicht sicher sein, dass 0.9 Schwelle --- Ich denke, es könnte in vielen Fällen deutlich niedriger sein und würde sich bei etwa 0,5 ziemlich unbehaglich fühlen. Ich denke, Sie können es nur in Ihrer Anwendung testen, aber im Zweifelsfall würde ich die deterministische Laufzeit bevorzugen. – Svante

0

Generieren Sie eine Zufallszahl R in der gesamten Domäne (subtrahieren Sie die Größe von N vom Maximalwert), die Sie verwenden möchten. Dann Schleife durch alle N kleiner als R und für jede addiere 1 bis R. Dies wird eine zufällige Zahl in der Domäne geben, die nicht in N.

+1

Das ist keine zufällige Zufallsgenerierung, weil es auf Kantenzahlen gewichtet wird - Zahlen, die nahe den Elementen in N sind. – aperkins

+0

Nein, weil es 1 zu R addiert, ob ein Konflikt vorliegt oder nicht. – murgatroid99

+1

Ja, weshalb es an den Rändern enden wird - Ihr R wird eher derjenige sein, der über einem in der Menge von N liegt als dies nicht der Fall ist - doppelt so wahrscheinlich. Eine Zahl direkt über der anderen zu treffen, würde 2/P werden, wobei P die gesamte verfügbare Menge an Zahlen ist und alle anderen Zahlen 1/P wären. Wenn Sie Zahlen in einer Reihe - sagen wir 2,3,4 - in der Menge hatten, dann steigt für jede Zahl in einer Reihe die Wahrscheinlichkeit, die darüber liegende zu treffen (4 in diesem Beispiel) um 1/P pro Zahl in eine Reihe nach der ersten (4/P in meinem Beispiel). – aperkins

1

Angesichts Ihrer begrenzten Beschreibung? Finde den maximalen Wert der Elemente in N. Erzeuge nur Zufallszahlen, die größer sind.

Verwandte Themen