Ich muss einen Pseudozufallszahlengenerator mit einer einstellbaren Periode erstellen. Außerdem dürfen innerhalb einer Frist keine Kollisionen auftreten. Das heißt, Folgendes muss true zurückgeben:

// prng is "generated" at run-time
// (though a by-hand solution would work)

bool test(func prng, int period) {
    int seed = 0;  // Any number should work
    int cur = seed;

    for (int i = 0; i <= period; ++i) {
        cur = prng(cur);

        if (cur == seed) {
            if (i == period) {
                // We hit our period on target
                return true;
            }

            // Period too low (we hit our seed already!)
            return false;
        }
    }

    // Period too high
    return false;
}

(Beispiel ist Pseudocode; eine Antwort in einer allgemein lesbaren Sprache (C ++, Python, Haskell usw.) ist akzeptabel.)

Das PRNG mussnich hängt beim Generieren der Zahlen vom veränderlichen statischen Zustand ab. Das heißt, ich kann keine große Tabelle mit bereits zurückgegebenen Nummern oder Ähnlichem haben. Es sollte sich nur auf die angegebene Eingabe stützen, um den nächsten Term zu generieren.

Der Algorithmus muss nicht (natürlich) kryptografisch stark oder "stark" zufällig sein. Jedoch,x % period Das ist nicht akzeptabel; es muss mindestens @ seetwa zufällig

Ich habe mich mit linearen Kongruenzgeneratoren befasst, aber das scheint der falsche Weg zu sein, um meine spezifischen Einschränkungen zu berücksichtigen.

(Brute-Forcing ist keine Option, es sei denn, es ist relativ schnell (ein paar Sekunden).)