動的計画法 - 組み合わせ

から、動的計画法による組み合わせの算出方法を学びましょう。

   Dynamic Programming

動的計画法

   Problem :- 
   Evaluate nCr i.e combination ( n, r ).
   Combination refer to the combination of n things taken r at a time without repetition.
   Mathematically, nCr = n! / r! * ( n - r )!

問題

nCr , つまり n個からr選んだときの全ての組み合わせを求めます。組み合わせ とは、n個から重複なしにr個選んだ数のこととします。

数学的には、 nCr = n! / r! * ( n - r ) ! になります

   Solution :-

解法

   Let C ( n , r ) denotes combination of n things taken r at a time.
   As per recursive formulation, C ( n , r ) = C ( n - 1 , r - 1 ) + C ( n - 1 , r ) with C ( n , 0 ) = C ( n , n ) = 1.
   This is basically the structure of an optimal solution defined recursively.

C ( n, r ) を一度に n から r とられるものと意味するものとしましょう。

再帰的に数式で表すと、 C ( n, r ) は C ( n - 1 , r - 1 ) + C ( n - 1 , r ) ただし C ( n , 0 ) = C ( n , n ) = 1 と書けます。

これは基本的に再帰的に定義される最適化された解法の構造です。

   We can maintain a 2D array C [ n + 1 ][ r + 1 ] which stores all the combination values starting from C ( 0 , 0 ). Finally, C [ n ][ r ] gives the value of C ( n , r ).
   See the program below for the solution.

われわれは、C ( n , r ) から始まる全ての組み合わせの値を保持する C [ n + 1 ][ r + 1 ] という２次元配列 を保持するようにする。

そうすると、最後には C [ n ] [ r ] は C ( n, r ) の答えを持つことになる。次のプログラムを見よ。

サンプルプログラム

元はC++だったが、勉強のためRubyで組み直した

## find C(n,r)
## Standard recursive formula for computing C(n,r)
## C(n,r) = C(n-1,r-1) + C(n-1,r)
## where C(n,0) = C(n,n) = 1

def choose(n, r)
  1 if r == 0 or r == n

  # store C(n,r) in a matrix
  c = Array.new(n+1).map{Array.new(r+1,0)}
  i,j = 0

  for i in 0..n
    # C(i,0) = 1 for i = 0...n
    c[i][0] = 1
  end
  for j in 0..r
    # if n = 0, C(n,r) = 0 for all 'r'
    c[0][j] = 0
  end

  for i in 1..n
    for j in 1..r
      if i == j
        # C(n,n) = 1
        c[i][j] = 1
      elsif j > i
        # case when r > n in C(n,r)
        c[i][j] = 0
      else
        # apply the standard recursive formula
        c[i][j] = c[i-1][j-1] + c[i-1][j]
      end
    end
  end

  return c[n][r]
end

n = 5
r = 2
comb = choose(n,r)

puts "C (#{n},#{r}) = #{comb}"

アルゴリズムを見える化

nCr , n = 3, r = 2 を求める

1. 行 n、列 r の格子を考える

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)
(3,0)	(3,1)	(3,2)

2. C(i,0) = 1 for i = 0...n

(0,0) = 1	(0,1)	(0,2)
(1,0) = 1	(1,1)	(1,2)
(2,0) = 1	(2,1)	(2,2)
(3,0) = 1	(3,1)	(3,2)

3. if n = 0, C(n,r) = 0 for all r

(0,0) = 0	(0,1) = 0	(0,2) = 0
(1,0) = 1	(1,1)	(1,2)
(2,0) = 1	(2,1)	(2,2)
(3,0) = 1	(3,1)	(3,2)

4. j と i、それぞれ 1から最大値まで

i == j であれば、１を設定（初期値っぽい）
j > i であれば、０を設定（計算に関係ないから）

それ以外は

c[i][j] = c[i-1][j-1] + c[i-1][j]
- 斜め左上のセルと上のセルを合計したものがそのセルの値

(0,0) = 0	(0,1) = 0	(0,2) = 0
(1,0) = 1	(1,1) = 1	(1,2) = 0
(2,0) = 1	(2,1) = 2	(2,2) = 1
(3,0) = 1	(3,1) = 3	(3,2) = 3

う〜ん？コレで本当に計算が早くなるのでしょうか？

参考サイト

【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた
- 40C20の答えは137,846,528,820(通り)、このような大規模な組み合わせに動的計画法は有効なようだ

動的計画法 - 組み合わせ