取り組んだ経緯
とある会社との面談の際に、再帰関数について質問されて、
まともに答えられず悔しかったので
タイトルに表記したアルゴリズム問題に挑戦して取り組んでみることにしました。
問題
- 数字の配列から数値を０〜n（配列数）個取った組み合わせを求める。
- 組み合わせの数字を合計し、その結果を重複なく出力する。
問題の具体例
- 数字の配列[1,2,3,4,5,6]がある
- 数字の配列を取りうるパターン（数式でnCr）を求める。
- nの最大値は6(配列の中身の数である)
- rの取り得る範囲は0~6
具体例の解き方
今回は、配列[1,2,3,4,5,6]から数値を０〜6個取った場合の合計数値の求め方を記載する
◆配列から数値を０個とる場合
_6 C_0 \\
数値は取らないので、合計値としては「０」
◆配列から数値を1個とる場合の合計値
_6 C_1 \\
結果は、[1,2,3,4,5,6]
◆配列から数値を2個とる場合の合計値
{_6 C_2} = (1 + {_5 C_1}) + (2 + {_4 C_1}) + (3 + {_3 C_1}) + (4 + {_2 C_1}) + (5 + {_1 C_1}) \\
配列から２つ取得すれば良いので、
考え方として、まず１つ取る数値を固定すると
上記数式のように取得数を減らした数式が入れ子形式できる。
取得方法についてイメージがしにくいので下記に記載する。
(1 + {_5 C_1}) の場合
[1,2],[1,3],[1,4],[1,5],[1,6]という配列の組み合わせができる。
今回は合計した数値を求めたいので、結果は下記のようになる
[3,4,5,6,7]
これを1〜５を先約して取得するパターンを実施した場合の結果は、
[3,4,5,6,7,5,6,7,8,7,8,9,9,10,11]という風になる
最終的に重複を削除して
__[3,4,5,6,6,8,9,10,11]__となる。
◆配列から数値を3個以上n未満取得する場合の合計値
{_6 C_r} = (1 + {_5 C_{r-1}}) + (2 + {_4 C_{r-1}}) + (3 + {_3 C_{r-1}}) + (4 + {_2 C_{r-1}}) \\
上記式でn=rとなった時点で、「切り出し数字＋数式」が終了する。
r＝３だと上記数式
r=4だと下記のようになり
{_6 C_4} = (1 + {_5 C_{3}}) + (2 + {_4 C_{3}}) + (3 + {_3 C_{3}})
\\
r=5だと下記のようになる。
{_6 C_5} = (1 + {_5 C_{4}}) + (2 + {_4 C_{4}})
\\
基本的に、入れ子構造となり、
r=5の場合で（1 + ５C4）の部分は下記となり、
(1 + {_5 C_{4}}) = (1 + (2 + {_4 C_{3}})) + (1 + (3 + {_3 C_{3}})) \\
新規に出現した（1 + (２＋4C3)）の部分は下記となり、
(1 + (2 + {_4 C_{3}})) = (1 + (2 + (3 + {_3 C_{2}}))) + (1 + (2 + (4 + {_2 C_{2}}))) \\
続いて、出現した(1+(２＋(3+3C2)))の部分は下記となる。
(1 + (2 + (3 + {_3 C_{2}}))) = (1 + (2 + (3 + (4 + {_2 C_{1}})))) + (1 + (2 + (3 + (5 + {_1 C_{1}})))) \\
◆配列から数値をn個取得する場合の合計値
配列の合計値を取得すれば良いので
結果は、1 + 2 + 3 + 4 + 5 + 6 = 21
問題を解くプログラム
入れ子構造を取るようにすれば良いので、
例題での考え方を反映してプログラムをかけば下記の通りになる
class Array
def combination_array(pick_num（nCrのrに相当）)
# 配列からゼロ個取る場合ゼロを返す
return 0 if pick_num == 0
# 配列から1個取る場合、配列の中身を１つずつ返す
return map { |e| e } if pick_num == 1
ret = []
# 先行して取得する数値の取るインデックス番号の範囲を0〜（n（配列数）-r（ピック数））繰り返す
(0..size（配列数） - pick_num).each do |i|
#切り出す数値
picked = self[i]
#[1,2,3]の配列があったとして、self[0]で１を抜き出し、rest = [2,3]の残りの配列を求める式
rest = self[i + 1..-1]
#残りの配列に対して、再度combination_arrayメソッドを実行する。nCr= n-1Cr-1の形式
rest.combination_array(pick_num - 1).each do |c|
ret << picked + c
end
end
#3C2 [1,2,3]があった場合、下記で[3,4,5]の最終結果を返す
ret
end
end
# 今回用意する数値の配列をXと表記する
numbers = Array(X)
# 結果を格納する配列を新規作成
answers = Array.new()
# 配列を取得する範囲を０個〜n個未満まで上記作成のコンビネーションメソッドを繰り返す。
for pick in 0..n-1
#上記メソッドの最終結果をanswers配列に格納
answers << numbers.combination_array(pick)
end
# 配列を全て取得した場合＝配列の中身の合計値を求める
answers << numbers.inject(:+)
# 配列の結果は[[1,2,3],[3,5,6,7],[7,9,10,32,44]]のようになっているのを
# flattenメソッドで[1,2,3,5,6,7,7,9,10,32,44]に修正
answers.flatten!
# uniqメソッドで重複している数値をなくす。
answers.uniq!
# 答えの出力。
puts answers
感想
再帰関数について、なんとなくわかったような状態になった気がします。
今後は、アルゴリズム問題に挑みつつ再帰関数の理解を深めたいと思います。
また、課題としては、負荷の少ない記述方法を考えて、
大規模演算の処理ができるようにすることだと考えております。