はこべにっき@bkc

和がnになるm数の組み合わせを求める

16:29 |

from

• 和がnになる2数の組み合わせを求める
• 和がnになる2数の組み合わせを求める - い〜さねっと
• ひさしぶりの日記 - 郡山からHello World

2数の和なので片方がわかれば，もう片方もわかる．

def cmb2(n)                                                    
  (0..n).map {|i| [i, n - i]}                                  
end

(0..3).each do |n|                                             
  p cmb2(n)                                                    
end 

一般化して，2数以上の和に対応できるようにした．例では4つの数に分けてる．

はじめとりあえず，２つにわけて，わけたりなければ片方をさらに2つにわけて…みたいなことを再帰でやってる．ちゃんと考えてないけどオーダーはn^2ではすんでない感じがする．

def cmb(n, m)
  return n if m <= 1

  pairs = (0..n).map {|i| [i, n - i]} # 上のcmb2といっしょ
  return pairs if m == 2

  result = []
  pairs.each do |pair|
    cmb(pair[1], m - 1).map do |second|
      result.push( [pair[0]] + second )
    end
  end
  result
end

(3..6).each do |n|
  puts n
  p cmb(n, 4)
end

3
[[0, 0, 0, 3], [0, 0, 1, 2], [0, 0, 2, 1], [0, 0, 3, 0], [0, 1, 0, 2], [0, 1, 1, 1], [0, 1, 2, 0], [0, 2, 0, 1], [0, 2, 1, 0], [0, 3, 0, 0], [1, 0, 0, 2], [1, 0, 1, 1], [1, 0, 2, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 2, 0, 0], [2, 0, 0, 1], [2, 0, 1, 0], [2, 1, 0, 0], [3, 0, 0, 0]]

6とかは量が爆発してるので略．重複を消すにはSetが良さそう．

追記

重複を消す && 和に0を含めないようした．全部計算してから，不要なのを取り除いてる．こういうのは遅延評価ができるHaskellが得意そう．

require 'set'

def _cmb(n, m)
  return n if m <= 1

  pairs = (0..n).map {|i| [i, n - i]}
  return pairs if m == 2

  result = []
  pairs.each do |pair|
    _cmb(pair[1], m - 1).map do |second|
      result.push( [pair[0]] + second )
    end
  end
  result
end

def cmb(n,m)
  results = Set.new
  _cmb(n,m).each do |c|
    result = c.sort.select {|i| i > 0}
    results.add(result) if result.size == m
  end
  results.to_a
end

(0..10).each do |n|
  puts n
  p cmb(n, 4)
end

0
[]
1
[]
2
[]
3
[]
4
[[1, 1, 1, 1]]
5
[[1, 1, 1, 2]]
6
[[1, 1, 2, 2], [1, 1, 1, 3]]
7
[[1, 2, 2, 2], [1, 1, 2, 3], [1, 1, 1, 4]]
8
[[1, 1, 1, 5], [2, 2, 2, 2], [1, 1, 3, 3], [1, 2, 2, 3], [1, 1, 2, 4]]
9
[[1, 2, 2, 4], [2, 2, 2, 3], [1, 2, 3, 3], [1, 1, 3, 4], [1, 1, 1, 6], [1, 1, 2, 5]]
10
[[1, 3, 3, 3], [1, 2, 2, 5], [1, 1, 4, 4], [1, 1, 3, 5], [1, 1, 1, 7], [2, 2, 2, 4], [1, 1, 2, 6], [2, 2, 3, 3], [1, 2, 3, 4]]