自然数を n 個に分割する & 重複組み合わせ(Ruby)
def divide(x, n) result = [] return [] if n.zero? return [[0] * n] if x.zero? return [[x]] if n == 1 0.upto(x) do |i| result += divide(x - i, n - 1).map {|a| a + [i]} end result end p divide(5, 3)
結果。5 を 3つに分割している。
[[5, 0, 0], [4, 1, 0], [3, 2, 0], [2, 3, 0], [1, 4, 0], [0, 5, 0], [4, 0, 1], [3, 1, 1], [2, 2, 1], [1, 3, 1], [0, 4, 1], [3, 0, 2], [2, 1, 2], [1, 2, 2], [0, 3, 2], [2, 0, 3], [1, 1, 3], [0, 2, 3], [1, 0, 4], [0, 1, 4], [0, 0, 5]]
これができれば重複組み合わせが簡単に実装できる。上の例だと、3つの中から重複を許して 5つ取る組み合わせを作ることができる。
実際に重複組み合わせを実装してみた。
def repeated_combination(ar, n) divide(n, ar.size).map do |a| result = [] a.each_with_index {|n, i| n.times {result << ar[i]}} result end end p repeated_combination([:a, :b, :c], 3)
結果。
[[:a, :a, :a], [:a, :a, :b], [:a, :a, :c], [:a, :b, :b], [:a, :b, :c], [:a, :c, :c], [:b, :b, :b], [:b, :b, :c], [:b, :c, :c], [:c, :c, :c]]
なお、もちろん Ruby 本体に重複組み合わせを得るメソッドはあります。