История изменений
Исправление maggotroot, (текущая версия) :
Твоя задача эквивалентна генерации случайной перестановки 1...N^2 без дополнительной памяти. Если ты хочешь сэмплить равномерно из всего пространства перестановок, то это невозможно сделать с памятью меньше чем O(N^2). Однако, если честность рандома не очень важна, то ты можешь без проблем сэмплить из подмножества. Например, шагая по i+2 (mod N), если N четно. Но я бы не советовал заниматься таким.
Исправление maggotroot, :
Твоя задача эквивалентна генерации случайной перестановки 1...N без дополнительной памяти. Если ты хочешь сэмплить равномерно из всего пространства перестановок, то это невозможно сделать с памятью меньше чем O(N). Однако, если честность рандома не очень важна, то ты можешь без проблем сэмплить из подмножества. Например, шагая по i+2 (mod N), если N четно. Но я бы не советовал заниматься таким.
Исходная версия maggotroot, :
Твоя задача эквивалентна генерации случайной перестановки 1...N без дополнительной памяти. Если ты хочешь сэмплить равномерно из всего пространства перестановок, то это невозможно сделать с памятью меньше чем O(N). Однако, если честность рандома не очень важна, то ты можешь без проблем сэмплить из подмножества. Например, шагая по i+2 (mod N), если N четно. Но я бы не советовал заниматься таким.
Но в твоей задаче памяти нужно только О(2*N): для последовательности внешнего и внутреннего обхода.