Random number generator, füllt ein Intervall

Wie würden Sie implementieren Sie einen Zufallszahlengenerator, der, gegeben ein Intervall, das (zufällig) generiert, die alle zahlen in diesem Intervall, ohne Wiederholung?

Sollte es verbrauchen so wenig Zeit und Speicher wie möglich.

Beispiel in einem nur erfunden, um C#-ruby-ish pseudocode:

interval = new Interval(0,9)
rg = new RandomGenerator(interval);
count = interval.Count //equals 10
count.times.do{
    print rg.GetNext() + " "
}

Diese Ausgabe sollte etwas wie :

1 4 3 2 7 5 0 9 8 6

InformationsquelleAutor Cristi Diaconescu | 2010-02-17

13

Füllen eines Arrays mit Intervall, und dann mische es.

Den standard-Weg, um shuffle ein array mit N Elementen ist, wählen Sie eine zufällige Zahl zwischen 0 und N-1 (sagen wir R), swap-und pos[R] mit Element[N]. Dann subtrahieren eines aus N, und wiederholen Sie, bis Sie bei N =1.
- Darauf hinzuweisen, dass der "standard" - shuffle, die Sie erwähnen, ist der Fisher-Yates-Durstenfeld-Algorithmus: en.wikipedia.org/wiki/...
InformationsquelleAutor James Curran
4

Diese hat kommen vor. Versuchen Sie es mit einem lineare feedback shift registrieren.

InformationsquelleAutor plinth
1

Einen Vorschlag, aber es ist speicherintensiv:

Den generator erstellt eine Liste aller zahlen im Intervall, und mischt es dann.

InformationsquelleAutor Cristi Diaconescu
1

Sehr effiziente Art und Weise zu mischen ein array von zahlen, wo jeder index ist einzigartig, stammt aus der Bildverarbeitung und wird verwendet, wenn die Anwendung der Techniken wie " pixel-auflösen.

Grundsätzlich beginnen Sie mit einer geordneten 2D-array und dann verschieben von Spalten und Zeilen. Diese Permutationen sind, die durch die Art und Weise einfach zu implementieren, Sie können sogar haben eine genaue Methode, die Ausbeute wird der resultierende Wert in x,y nach n Permutationen.

Die grundlegende Technik, beschrieben auf einem 3x3-raster:

1) Beginnen Sie mit einer geordneten Liste, jede Zahl darf nur einmal existieren
```
0 1 2
3 4 5
6 7 8
```
2) Wählen Sie eine Zeile/Spalte, die Sie möchten, zu mischen, einen Schritt Voraus. In diesem Fall bin ich die Verschiebung der zweiten Zeile auf der rechten Seite.
```
0 1 2
5 3 4
6 7 8
```
3) Wählen Sie eine Zeile/Spalte, die Sie möchten, zu mischen... ich suffle der zweiten Spalte nach unten.
```
0 7 2
5 1 4
6 3 8
```
4) Holen ... Zum Beispiel, erste Zeile, auf der linken Seite.
```
2 0 7
5 1 4
6 3 8
```
Wiederholen Sie diese Schritte so oft wie Sie wollen. Sie können immer tun, diese Art der transformation auch auf ein 1D array. Also dein Ergebnis wäre jetzt [2, 0, 7, 5, 1, 4, 6, 3, 8].

InformationsquelleAutor Joa Ebert
1

Einer gelegentlich sinnvolle alternative zum shuffle Ansatz ist der Einsatz einer subscriptable set-container. Bei jedem Schritt, wählen Sie eine zufällige Zahl 0 <= n < count. Extrahiert das N-te Element aus der Menge.

Das Hauptproblem ist, dass typische Container nicht verarbeiten kann diese effizient. Ich habe es mit bit-Vektoren, aber es funktioniert nur gut, wenn die größte möglich Mitglied zu werden, ist relativ klein, aufgrund der linearen Abtastung der bitvector finden musste, die N-te gesetzte bit.

99% der Zeit, der beste Ansatz ist, zu mischen, wie andere vorgeschlagen haben.

BEARBEITEN

Ich verpasste die Tatsache, dass ein einfaches array ist ein gutes "set" - Datenstruktur - Fragen Sie mich nicht warum, ich habe es vor. Der "trick" ist, dass Sie sich nicht sorgen, ob die Elemente im array sortiert oder nicht sortiert. Bei jedem Schritt, Sie wählen nach dem Zufallsprinzip, und extrahieren Sie es. Zum füllen der leeren slot (ohne shift durchschnittlich die Hälfte Ihrer Artikel einen Schritt nach unten) Sie bewegen nur den aktuellen end-Element in den leeren Steckplatz in konstanter Zeit, dann reduzieren Sie die Größe des Arrays um eins.

Zum Beispiel...
```
class remaining_items_queue
{
  private:
    std::vector<int>  m_Items;

  public:
    ...

    bool Extract (int &p_Item);  // return false if items already exhausted
};

bool remaining_items_queue::Extract (int &p_Item)
{
  if (m_Items.size () == 0)  return false;

  int l_Random = Random_Num (m_Items.size ());
    // Random_Num written to give 0 <= result < parameter

  p_Item = m_Items [l_Random];

  m_Items [l_Random] = m_Items.back ();
  m_Items.pop_back ();
}
```
Der trick ist es, einen Zufallszahlengenerator, der gibt (mit einem halbwegs gleichmäßige Verteilung) zahlen im Bereich von 0 bis n-1, wo n ist potenziell jedes mal anders. Die meisten standard-random-Generatoren geben Sie einen festen Bereich. Obwohl die folgenden NICHT geben eine gleichmäßige Verteilung, es ist oft gut genug...
```
int Random_Num (int p)
{
  return (std::rand () % p);
}
```
std::rand gibt zufällige Werte im Bereich von 0 <= x < RAND_MAX, wobei RAND_MAX ist die Umsetzung definiert.

InformationsquelleAutor Steve314
0
1. Nehmen Sie alle zahlen in dem Intervall, setzen Sie Sie auf Liste/array
2. Shuffle die Liste/array
3. Schleife über die Liste/array
InformationsquelleAutor Juha Syrjälä
0

Eine Möglichkeit ist die Erzeugung einer geordneten Liste (0-9) in deinem Beispiel.

Dann verwenden Sie die random-Funktion zu wählen Sie ein Element aus der Liste. Entfernen Sie das Element aus der Liste und fügen Sie es dem Schwanz neue.

Der Prozess ist abgeschlossen, wenn die ursprüngliche Liste leer ist.

Ausgabe der neuen Liste.

InformationsquelleAutor ChrisF
0

Können Sie eine linear congruential generator mit Parametern zufällig gewählt, sondern so, dass es erzeugt den vollen Zeitraum. Sie müssen vorsichtig sein, weil die Qualität der Zufallszahlen kann schlecht sein, je nach den Parametern.
- Wie stellen Sie sicher, dass ein LCG deckt alle zahlen in dem Intervall? z.B. wikipedia-Beispiel x(n+1) = 3*x(n) + 1 nicht...
- Ihr Beispiel nicht Bedingung 3 der en.wikipedia.org/wiki/...
- Ja, du hast Recht; ich failed to denken, dass Sie in einer LCG-sobald Sie wiederholt eine Zahl, Sie beginnen mit der Sequenz.
InformationsquelleAutor starblue

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.