Мне нужно создать на месте генератор псевдослучайных чисел с регулируемым периодом. Кроме того, в течение одного периода не должно быть столкновений. То есть следующее должно возвращать true:

// 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;
}

(Примером является псевдокод; приемлем ответ на любом общедоступном языке (C ++, Python, Haskell и т. Д.).)

PRNG долженне зависит от изменяемого статического состояния при генерации чисел. То есть у меня не может быть большой таблицы уже возвращенных чисел или чего-то в этом роде. Он должен полагаться только на данные входные данные для генерации следующего члена.

Алгоритм не обязательно должен быть криптографически сильным (конечно) или «сильно» случайным. Тем не мение,x % period не приемлемо; это должно быть по крайней мерев некотором роде случайным образом.

Я изучил линейные конгруэнтные генераторы, но это, кажется, неправильный путь для моих конкретных ограничений.

(Перебор не возможен, если он не является относительно быстрым (несколько секунд).)