4

次から始まる、数値の配列で表されるカウンターをプログラムしたいと思います。

[0, 0, 0]

ここでの制約は、各ポジションの上限が異なるため、必ずしも 9 などであるとは限りませんが、指定されているということです。例えば：

[4, 2, 1]

これは、次の増分シーケンスにつながります。

[0, 0, 0]
[0, 0, 1] 
[0, 1, 0]
[0, 1, 1]
[0, 2, 0]
[0, 2, 1]
[1, 0, 0]
.
.
.

もちろん、モジュロを使用して各キャリーオーバーを次の位置に追加するソリューションを考えることができます。しかし、誰かがこれを効率的に実装する方法を考えていますか?

それは私の素朴な実装です:

max = [10, 1, 1, 1, 10]
counter = [0, 0, 0, 0, 0]

i = counter.length-1
while counter != max do
   counter[i] = counter[i] + 1
   while counter[i] > max[i]
      counter[i] = 0
      i = i - 1
      counter[i] = counter[i] + 1
   end
   i = counter.length-1
 end
4

3 に答える 3

3

効率についてはわかりませんが、これが私のショットです：

start = [0, 0, 0]
cap = [4, 2, 1]

start.zip(cap).map{ |i, c| (i..c).to_a }.reduce(&:product).map &:flatten

次のようなものを生成します。

[[0, 0, 0],
 [0, 0, 1],
 [0, 1, 0],
 [0, 1, 1],
 [0, 2, 0],
 [0, 2, 1],
 [1, 0, 0],
 [1, 0, 1],
 [1, 1, 0],
 [1, 1, 1],
 [1, 2, 0],
 [1, 2, 1],
 [2, 0, 0],
 [2, 0, 1]...]
于 2013-02-03T05:33:32.280 に答える
2

編集：編集を行う前にこれを書いていました。リストを出力するだけでなく、カウンターオブジェクトが必要なようでした。

1) 制限ではなく、各桁の (制限 + 1) を指定することをお勧めします。たとえば、[秒、分、時、日、年] カウンターの場合、[59,59,23,364] ではなく [60, 60, 24, 365] と書く方が (私にとっては) 理にかなっています。

2) カウンターが配列の最後の制限をオーバーフローした場合の対処方法を理解する必要があります。無限に数えられる余分な位置を追加しました。

3) 添え字の反転を避けるために、少なくとも内部表現では、配列の順序を逆にすることもお勧めします。そのようにしたくない場合は.reverse、basesインinitializeアンド@digitsインできますto_s

class MyCounter 
  def initialize bases
    @bases = bases
    @bases << 1.0/0 # Infinity
    @digits = Array.new(bases.size, 0)
    prod = 1
    @digit_values = [1] + @bases[0..-2].map { |b| prod *= b }
  end

  attr_reader :digit_values

  def to_s
    @digits
  end

  def increment(digit=0)
    v = @digits[digit] + 1
    if v < @bases[digit]
      @digits[digit] = v
    else 
      @digits[digit] = 0
      increment(digit+1)
    end
    self
  end

  def +(integer)
    (@digits.size - 1).step(0,-1).each do |i|
      @digits[i] += integer / @digit_values[i]
      integer = integer % @digit_values[i]
    end
    self
  end
end

c1 = MyCounter.new [2,3,5]
20.times { c1.increment; p c1 }

c2 = MyCounter.new [2,3,5]
c2 += 20
p c2
于 2013-02-03T06:36:44.203 に答える
0

0からcapまでの値で、キャップごとに配列を作成します。最初の配列を取得し、残りの配列でデカルト積を計算します。

caps = [4, 2, 1]
arrs = caps.map{|cap| (0..cap).to_a} #=>[[0, 1, 2, 3, 4], [0, 1, 2], [0, 1]]
p arrs.shift.product(*arrs)
# =>[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [0, 2, 0], [0, 2, 1], ...

結果とともにメモリを消費する配列が必要ない場合は、ブロックを指定します。product各要素を1つずつ生成します。

arrs = caps.map{|cap| (0..cap).to_a}
arrs.shift.product(*arrs){|el| puts el.join} #no resulting array
#000
#001
#010
#011
#...
于 2013-02-03T23:03:43.657 に答える