2

我们必须{1,2,3,..,n}在O(1)空间中生成数组。
我能够在O(n)太空中做到这一点。

我O(n)通过首先存储数组然后将其随机化来完成空间解决方案。但是如何在不将数组存储在O(1)空间中的情况下做到这一点。

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

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

4

4 回答 4

2

我已经构建了一个线性反馈移位寄存器生成器解决方案，我认为它可以满足您的要求。该实现基于斐波那契 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
于 2015-08-25T00:28:46.223 回答
1

如果 n 是 2 的幂，则可以使用块大小为 n 位的块密码来生成 n 个元素的排列 - 只需写出 Encrypt(0), Encrypt(1)... Encrypt(n-1) .

如果 n 不是 2 的幂，则令 m 是 n 的 2 的第一次幂。加密 0..n-1，如果结果 >= n，则再次加密，直到得到一个范围内的值。这相当于将 m 个元素的排列写成一个循环，然后删除 >= n 的元素。

如果您没有所需大小的标准分组密码，您可以使用 Luby-Rackoff aka Feistel 构造来创建一个使用散列函数作为https://en.wikipedia.org/wiki中的 F 操作的密码/Feistel_cipher. Feistel 网络的一个特点是 F() 产生多于一位，被视为排列，它们从不产生奇数排列：如果 Feistel 输出为 k 位宽，则每轮产生 2^(k-1) 的某个倍数 2-循环，这会产生 k > 1 的均匀排列，因此您可能需要稍微考虑一下和/或使用具有不同反馈风格的多个 Fe​​istel 轮来从中获得合理的随机排列。具有 1 位 Feistel 输出的适当精细的 Fiestel 轮系统可以被视为交换网络的隐式构造，可用于实现网络中的任意排列。

于 2015-08-24T18:11:39.437 回答
-1

严格来说，O(1)解决方案是不可能的，因为数字n本身需要log(n)位来存储。

另一方面，如果练习的目标是避免使用n整数数组，并且您愿意牺牲一些严谨性 - 即假设n! 可以在内存中表示- 解决方案是在 rangeO(1)中生成一个随机数，并计算k-th permutation，在计算时打印数字。k[0, n!)

于 2015-08-24T20:14:57.470 回答
-2

一般来说，这是一个不可能的问题。尽管可以在列表之外没有任何内存的情况下重新组织列表并留下统计上的随机列表，但真正的随机列表是不可能的。

如果将问题解释为数字流过滤器，那么在任何时间点我们都只能看到流的一个元素。我们可以看到流中尚未处理的部分是有帮助的，但是如果我们不能改变那部分，我们就会被卡住。

完美混合列表的两种基本方法（给定一个完美的随机数生成器）：

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.

列表的真正随机手段可以简化为这两种方法之一。不幸的是，这两种方法都不能与没有随机写入权限的一次性过滤器一起使用。第一个需要修改列表中尚未创建的部分。第二个需要修改已经打印出来的部分列表。

于 2015-08-24T19:14:50.493 回答