在 O(n) 时间和 O(1) 空间中生成数组的随机排列

我们必须生成数组{1,2,3,..,n} in O(1) space.
我能够做到O(n) space.

I did O(n)空间解决方案，首先存储数组，然后将其随机化。但是如何在不存储数组的情况下做到这一点O(1) space.

我只是生成随机数，而不是存储它们，我需要打印它们，因为存储需要 O(n) 空间，但我需要在 O(1) 空间中进行，我的疑问是，如果我们继续生成随机数并且打印它们，可能有一些 1 到 n 之间的数字可能会生成多次，有些可能不会生成。那么如何在 O(1) 空间中将所有数字精确打印一次呢？

P.S.-我没有得到任何数组。输入只是“n”，我必须在 O(n) 时间和 O(1) 空间中打印数组 {1,2,3,...,n} 的排列。

我已经构建了一个线性反馈移位寄存器生成器解决方案，我认为它满足您的要求。该实现基于斐波那契 LFSR，因此它可以实现给定位数的完整周期。我继续输入最多 19 位的多项式系数，并根据指定的值选择适当的系数集N。生成的值大于N被卡入水中，但整个周期中的值总数小于2N所以它会产生你的N值在O(N)时间。 LFSR 保留一个状态字，所以它是O(1) space.

下面是 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