トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

DP - 組み合わせ

[アルゴリズム]

DP - 組み合わせ

  問題設定

csegeek.com - Find Combination C(n,r) using dynamic programming - Algorithms Tutorial

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

   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 ] という2次元配列 を保持するようにする。

そうすると、最後には 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 であれば、1を設定(初期値っぽい)
  • j > i であれば、0を設定(計算に関係ないから)

それ以外は

  • 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

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

参考サイト

お名前: コメント: