2

空間で配列を生成する必要があり{1,2,3,..,n}ます。 私は宇宙でそれを行うことができます。O(1)
O(n)

O(n)最初に配列を保存してから、その場でランダム化することにより、スペースソリューションを実行しました。しかし、配列をO(1)スペースに格納せずにそれを行う方法。

私は乱数を生成しているだけで、保存する代わりにそれらを印刷する必要があります。保存には O(n) スペースが必要ですが、O(1) スペースでそれを行う必要があり、乱数を生成し続けて、それらを印刷すると、複数回生成される可能性のある 1 から n までの数と、生成されない可能性のある数が存在する可能性があります。では、O(1) 空間にすべての数値を 1 回だけ出力するにはどうすればよいでしょうか?

PS-私は配列を与えられていません。入力は単に「n」であり、配列 {1,2,3,...,n} の順列を O(n) 時間と O(1) 空間で出力する必要があります。

4

4 に答える 4

2

あなたの要件を満たすと思われる線形フィードバックシフトレジスタジェネレーターソリューションを構築しました。実装はフィボナッチ LFSR に基づいているため、指定されたビット数で完全なサイクルを実現します。先に進み、最大 19 ビットの多項式係数を入力し、指定された の値に基づいて適切な係数セットを選択しましたN。生成された値はN船外に排出されますが、サイクル全体の値の総数はそれよりも少ないため、時間内に値2Nが生成されます。LFSR は 1 ワードの状態を保存するので、それはスペースです。NO(N)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

厳密に言えば、数値自体を格納するのにビットが必要O(1)なため、解決策は不可能です。nlog(n)

一方、演習の目的が整数の配列を回避することであり、厳密さをいくらか犠牲にすることを厭わない場合 (つまり、メモリ内で表現できるnと仮定する場合)、解決策はrangeで乱数を生成し、 を計算することです。 k-th permutation、計算した数値を出力します。n! O(1)k[0, n!)

于 2015-08-24T20:14:57.470 に答える