自然数を 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 本体に重複組み合わせを得るメソッドはあります。