产生在O（n）时间及O（1）空间随机排列一个数组 [英] to generate random permutation of a array in O(n) time and O(1) space

问题描述

我们不得不产生阵列 {1,2,3，...，N} 在 O（1）空间。
我能做到这一点在 O（N）的空间。

We have to generate Array {1,2,3,..,n} in O(1) space.
I am able to do it in O(n) space.

我做了 O（N）空间第一存储阵列，然后随机到位的解决方案。但如何做没有存储阵列中的 O（1）的空间。

I did O(n) space solution by first storing the array and then randomizing it in place. But how to do it without storing array in O(1) space.

我只是在产生随机数，而不是存储他们，我需要打印出来作为存储需要O（n）的空间，但我需要做的是在O（1）空间，什么我的疑问是，如果我们继续产生随机数，并打印出来，可能会有一些数字1之间到n可被产生一次以上，有些人可能不会生成。那么，如何设法为O打印所有数字只出现一次（1）空间？

I m just generating random number and instead of storing them I need to print them as storing would require O(n) space but I need to do it in O(1) space and what my doubt is if we go on generating random number and print them there may be some numbers between 1 to n which may be generated more than once and some may not be generated. So How do I manage to print all numbers exactly once in O(1) space?

P.S.-我没有给任何数组。输入仅仅是n然后我必须打印阵列的排列{1,2,3，...，N}在O（n）时间及O（1）空间。

P.S.- I am not given any array. Input is just 'n' and I have to print the permutation of array {1,2,3,...,n} in O(n) time and in O(1) space.

推荐答案

我已经建立了一个线性反馈移位寄存器产生的解决方案，我想满足你的要求。的实现是基于斐波的LFSR，因此它达到全周期为的比特的给定数目。我继续把在多项式系数高达19位，并选择基础上的 N 规定值的相应系数组。生成的值大于 N 落水得到打发，但在整个周期值的总数小于 2N 等等它会产生你的 N 在 O（N）时间值。状态的线性反馈移位寄存器preserves一个字，所以它的 O（1）的空间。

I've built a linear-feedback-shift-register generator solution which I think meets your requirements. The implementation is based on Fibonacci LFSRs, so it achieves full cycle for the given number of bits. I went ahead and put in the polynomial coefficients for up to 19 bits and select the appropriate coefficient set based on the specified value of N. Generated values greater than N get chucked overboard, but the total number of values in the full cycle is less than 2N so it will produce your N values in O(N) time. The LFSR preserves one word of state, so it's O(1) space.

下面是在Ruby中实现：

Here is the implementation in 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

这篇关于产生在O（n）时间及O（1）空间随机排列一个数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！