アルゴリズム問題: 1000円ちょうど

問題

10円, 50円, 100円, 500円が眼の前に無限にある。 この中から2枚 ~ 15枚を選んで、1000円ちょうどをつくる方法は何通りあるか?

解答

result = (2..15).flat_map { |num|
  ary = [10, 50, 100, 500].repeated_combination(num)
    .select { |coin_set|
      coin_set.inject(:+) == 1000
    }
}

p result.count

解説

"10円、50円、100円、500円からn枚を選択する(重複を許可する)"をつくる。 "重複を許可した組み合わせ" をつくるアルゴリズムを作成するのが大変そうだなぁと思ったところで Rubyのエグエグしいメソッドを発見

repeated_combination(Array)

array.repeated_combination(n) {|arr| block }

repeated_combinationメソッドは、配列の要素から引数n個を選んだときの重複組合せ（順序なし、重複を許す組合せ）を数え上げます。組合せの数だけブロックを繰り返し実行し、ブロック引数arrに組合せを配列で入れます。戻り値はレシーバ自身です。 次の例は、4個の数から3個を選んだときの重複組合せです。20通りの組合せができます。

つまるところこういうことだ

[10, 50, 100, 500].repeated_combination(2).to_a
=> [[10, 10], [10, 50], [10, 100], [10, 500], [50, 50], [50, 100], [50, 500], [100, 100], [100, 500], [500, 500]]

すごい。こんど内部実装読み解いて勉強しよう。 これを使えば、2 ~ 15枚を選ぶは以下のように表現ができる

result = (2..15).flat_map { |num|
  ary = [10, 50, 100, 500].repeated_combination(num).to_a
}

そしてこの中から合計が1000円になるものだけを抽出すれば良い。

result = (2..15).flat_map { |num|
  ary = [10, 50, 100, 500].repeated_combination(num)
    .select { |coin_set|
      coin_set.inject(:+) == 1000
    }
}