Более конкретно, существует ли алгоритм, который может генерировать, детерминистически, предоставленный начальный элемент, n целых чисел от 0 до (n-1), без дубликатов или пропущенных чисел, в линейном или сублинейном времени и постоянном пространстве?
Все ответы, которые я нашел или увидел в Интернете, требуют линейного пробела, поскольку им нужно хранить информацию о каждой цифре в последовательности, прежде чем они вообще смогут дать первое число.Это становится неоправданным использованием памяти в миллионах / триллионах возможных чисел, что полезно для генерации случайных идентификаторов.Есть ли алгоритм, скажем, итеративная формула, который приятно выплевывает одно число за другим, не имея необходимости знать какую-либо информацию обо всех числах до или после него?Или я сейчас живу в несбыточной мечте?