Wie Mersenne Twister verwenden, um alle Werte zwischen zwei Zahlen genau einmal zu generieren

Question

Ich würde mt19937 verwenden, um über ein Array zu schleifen und jeden Wert davon genau einmal, aber in zufälliger Reihenfolge. Gibt es im Wesentlichen eine Möglichkeit, mt19937 zu verwenden, um alle Zahlen innerhalb eines bestimmten Bereichs genau einmal zu erzeugen (ohne Duplikate zu ignorieren, aber sicherzustellen, dass es keine Duplikate insgesamt erzeugt (aus Gründen der Effizienz))?

Ich habe eine Shuffle-Funktion in Betracht gezogen, aber es sind nur die Indizes, die mir wichtig sind; Die Werte innerhalb des Arrays sind willkürlich, aber ihr entsprechender Index ist wichtig. Ich habe eine Matrix von 1, und ich muss zufällig einen Index auswählen und diese 1 zu einer 0 machen. Aber ich möchte diese Berechnung nicht mehr als nötig durchführen (genau so viele Elemente wie in der Matrix).

Answer 1

Sie müssen also eine Liste von Werten erstellen und sie dann mischen.

Während es eine Funktion zum Mischen gibt, ist der Algorithmus einfach. Beginne bei Index 0 und tausche mit einem zufälligen Wert im Bereich von 0 bis N-1, gehe dann zu Index 1 und tausche mit einem zufälligen Wert im Bereich von 1 bis N-1, und tausche nicht bei 0 bis N-1 liefert keine wirklich zufällige Permutation.

Answer 2

Ihren Array Unter der Annahme von Größe N und Sie nicht wollen, es neu zu ordnen:

1. generiert eine zweite Anordnung, auch die Größe N.
2. Mischen Sie das zweite Array mit der Fisher-Yates-Knuth shuffle.
3. Verwenden Sie die Elemente des ersten Arrays in der Reihenfolge, die vom zweiten Array angegeben wird.

Der Fisher-Yates-Knuth Shuffle kann wie folgt realisiert werden:

std::shuffle(a.begin(), a.end(), std::default_random_engine(seed));