для генерации случайной перестановки массива за время O (n) и пространство O (1)

Я создал генератор регистров сдвига с линейной обратной связью, который, как мне кажется, соответствует вашим требованиям. Реализация основана на LFSR Фибоначчи, поэтому она обеспечивает полный цикл для заданного количества битов. Я пошел дальше и ввел полиномиальные коэффициенты до 19 бит и выбрал соответствующий набор коэффициентов на основе указанного значения N. Сгенерированные значения, превышающие N, выбрасываются за борт, но общее количество значений в полном цикле меньше 2N, поэтому ваши N значения будут получены за O(N) времени. LFSR сохраняет одно слово состояния, поэтому это пробел O(1).

Вот реализация на Ruby:

#!/usr/bin/env ruby -w

# Linear Feedback Shift Register generator which operates on smallest bit
# range possible for a specified integer range, and skips over values outside
# the specified range. Since this attains full cycle length for the specified
# number of bits, and the number of bits is minimized relative to the specified
# N, the total number of iterations is bounded by 2N and is therefore O(N).
class LFSR
  # Polynomials for maximal LFSRs determine shift amounts for up to 19 bits.
  # See https://en.wikipedia.org/wiki/Linear_feedback_shift_register for
  # details. Add more entries if you need more than 19 bits.
  SHIFT_AMT = [
    [], [], [1], [1], [1], [2], [1], [1], [2, 3, 4], [4], [3], [2],
    [1, 2, 8], [1, 2, 5], [1, 2, 12], [1], [2, 3, 5], [3], [7], [1, 2, 5]
  ]

  # Constructor for the LFSR.  Specify the N and seed value.
  def initialize(n, seed)
    @n = n
    @state =  (seed % n) + 1
    @num_bits = Math.log2(n).floor + 1
  end

  # Generate the next iterate of the LFSR.  If it's above the specified N,
  # keep trying until you're done.
  def next_value
    loop do
      bit = @state
      SHIFT_AMT[@num_bits].each { |amt| bit ^= (@state >> amt) }
      @state = ((@state >> 1) | ((bit & 1) << (@num_bits - 1)))
      return @state if @state <= @n
    end
  end
end

N = (ARGV.shift || 100).to_i # Specify the 'N' value on cmd line. Default = 100
SEED = (ARGV.shift || 0x7FFF).to_i # Optionally specify a "seed" for the LFSR
my_lfsr = LFSR.new(N, SEED)  # Instantiate an LFSR object
N.times { p my_lfsr.next_value }   # Invoke it N times, print the results

Если n равно степени 2, блочный шифр с размером блока n бит может использоваться для генерации перестановки n элементов — просто запишите Encrypt(0), Encrypt(1)... Encrypt(n-1) .

Если n не является степенью числа 2, пусть m будет первой степенью числа 2 выше n. Зашифруйте 0..n-1, и если результат >= n, зашифруйте его снова, пока не получите значение в пределах диапазона. Это равносильно записи перестановки m элементов в виде цикла, а затем удалению элементов >= n.

Если у вас нет стандартного блочного шифра требуемого размера, вы можете использовать конструкцию Luby-Rackoff, также известную как Feistel, чтобы создать его, используя хеш-функцию в качестве F-операции в https://en.wikipedia.org/wiki/Feistel_cipher. Особенность сетей Фейстеля, в которых F() производит более одного бита, рассматриваемого как перестановки, заключается в том, что они никогда не производят нечетных перестановок: если выход Фейстеля имеет ширину k бит, каждый раунд дает число, кратное 2^(k-1) 2- циклов, что дает четную перестановку для k > 1, поэтому вы можете немного подумать об этом и/или использовать несколько раундов Фейстеля с разными стилями обратной связи, чтобы получить из этого достаточно случайные перестановки. Надлежащим образом разработанную систему раундов Фистеля с 1 битом выходных данных Фейстеля можно рассматривать как неявную конструкцию сети обмена, которую можно использовать для реализации произвольных перестановок в сетях.

Строго говоря, решение O(1) невозможно, потому что само число n занимает для хранения log(n) бит.

С другой стороны, если цель упражнения состоит в том, чтобы избежать массива из n целых чисел, и вы готовы пожертвовать некоторой строгостью, а именно предположить, что n! может быть представлено в O(1) памяти, решение состоит в том, чтобы сгенерировать случайное число k в диапазоне [0, n!) и вычислить k-я перестановка, печатающая числа по мере их вычисления.

В общем, это неразрешимая проблема. Хотя можно реорганизовать список без какой-либо памяти за пределами списка и остаться со статистически случайным списком, настоящий случайный список невозможен.

Если задачу интерпретировать как фильтр числового потока, то в любой момент времени мы можем видеть только один элемент потока. Помогает то, что мы можем видеть часть потока, которую еще предстоит обработать, но если мы не можем изменить эту часть, мы застряли.

Два основных способа идеального смешивания списка (при наличии идеального генератора случайных чисел):

for each element in the list:
  select a random element later in the list.
  swap.

for each element in the list:
  select a random element earlier in the list.
  swap.

По-настоящему случайное обращение к списку можно свести к одному из этих двух методов. К сожалению, оба эти метода не могут работать с однопроходным фильтром, у которого нет разрешения на произвольную запись. В первом нужно изменить часть списка, которая еще не создана. Второй нужно изменить часть уже распечатанного списка.