Einzigartige (sich nicht wiederholende) Zufallszahlen in O(1)?

Question

Ich würde gerne eindeutige Zufallszahlen zwischen 0 und 1000 generieren, die sich nie wiederholen (d.h. 6 taucht nicht zweimal auf), aber dafür nicht auf so etwas wie eine O(N)-Suche der vorherigen Werte zurückgreifen. Ist dies möglich?

Answer 1

Nehmen wir an, Sie möchten die gemischten Listen immer wieder durchgehen, ohne die O(n) verzögern Sie jedes Mal, wenn Sie neu anfangen zu mischen, in diesem Fall können wir dies tun:

1. Erstellen Sie 2 Listen A und B, mit 0 bis 1000, nimmt 2n Raum.

2. Mischen der Liste A mit Fisher-Yates, nimmt n Zeit.

3. Wenn Sie eine Zahl ziehen, mischen Sie die andere Liste in einem Schritt nach dem Fisher-Yates-Prinzip.

4. Wenn sich der Cursor am Ende der Liste befindet, wechseln Sie zur anderen Liste.

Vorverarbeiten

cursor = 0

selector = A
other    = B

shuffle(A)

Zeichnen Sie

temp = selector[cursor]

swap(other[cursor], other[random])

if cursor == N
then swap(selector, other); cursor = 0
else cursor = cursor + 1

return temp

Answer 2

Eine andere Möglichkeit:

Sie können ein Array von Flags verwenden. Und den nächsten nehmen, wenn er bereits ausgewählt ist.

Aber Vorsicht, nach 1000 Aufrufen wird die Funktion niemals enden, also müssen Sie eine Sicherung vornehmen.

Answer 3

Wenn N größer als 1000 ist und Sie K Stichproben ziehen müssen, können Sie eine Menge verwenden, die die bisherigen Stichproben enthält. Für jede Ziehung verwenden Sie Rückweisungsprobenahme was eine "fast" O(1)-Operation ist, so dass die Gesamtlaufzeit fast O(K) mit O(N)-Speicher beträgt.

Dieser Algorithmus stößt auf Kollisionen, wenn K "nahe" N ist. Das bedeutet, dass die Laufzeit viel schlechter als O(K) ist. Eine einfache Lösung besteht darin, die Logik umzukehren, so dass für K > N/2 alle Stichproben, die noch nicht gezogen wurden, aufgezeichnet werden. Bei jeder Ziehung wird eine Stichprobe aus der Ablehnungsmenge entfernt.

Das andere offensichtliche Problem mit dem Rejection Sampling ist, dass es sich um O(N)-Speicher handelt, was eine schlechte Nachricht ist, wenn N in die Milliarden oder mehr geht. Es gibt jedoch einen Algorithmus, der dieses Problem löst. Dieser Algorithmus wird nach seinem Erfinder Vitter's Algorithmus genannt. Der Algorithmus wird wie folgt beschrieben ici . Das Wesentliche an Vitters Algorithmus ist, dass nach jeder Ziehung ein zufälliger Übersprung anhand einer bestimmten Verteilung berechnet wird, die eine gleichmäßige Stichprobe garantiert.

Answer 4

Bei den meisten Antworten wird nicht garantiert, dass sie nicht zweimal dieselbe Nummer zurückgeben. Hier ist eine richtige Lösung:

int nrrand(void) {
  static int s = 1;
  static int start = -1;
  do {
    s = (s * 1103515245 + 12345) & 1023;
  } while (s >= 1001);
  if (start < 0) start = s;
  else if (s == start) abort();

  return s;
}

Ich bin mir nicht sicher, ob die Einschränkung gut spezifiziert ist. Man nimmt an, dass sich nach 1000 anderen Ausgaben ein Wert wiederholen darf, aber das lässt naiverweise zu, dass 0 unmittelbar auf 0 folgt, solange sie beide am Ende und am Anfang von 1000er-Sätzen erscheinen. Umgekehrt ist es zwar möglich, einen Abstand von 1000 anderen Werten zwischen den Wiederholungen einzuhalten, doch führt dies zu einer Situation, in der sich die Sequenz jedes Mal auf genau dieselbe Weise wiederholt, weil kein anderer Wert außerhalb dieser Grenze aufgetreten ist.

Hier ist eine Methode, die immer mindestens 500 andere Werte garantiert, bevor ein Wert wiederholt werden kann:

int nrrand(void) {
  static int h[1001];
  static int n = -1;

  if (n < 0) {
    int s = 1;
    for (int i = 0; i < 1001; i++) {
      do {
        s = (s * 1103515245 + 12345) & 1023;
      } while (s >= 1001);
      /* If we used `i` rather than `s` then our early results would be poorly distributed. */
      h[i] = s;
    }
    n = 0;
  }

  int i = rand(500);
  if (i != 0) {
      i = (n + i) % 1001;
      int t = h[i];
      h[i] = h[n];
      h[n] = t;
  }
  i = h[n];
  n = (n + 1) % 1001;

  return i;
}

Answer 5

Fischer Yates

for i from n1 downto 1 do
     j  random integer such that 0  j  i
     exchange a[j] and a[i]

Es ist eigentlich O(n-1), da man nur einen Tausch für die letzten beiden
Dies ist C#

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}