Ruby - 順列と組み合わせのまとめ
データ分析やゲームなどでパターンの組み合わせや順列が欲しい場合が多いと思います。
Ruby では Array クラスにこれらを生成する便利なメソッドが定義されています。
組み合わせ(combination)
N個の要素からM個を取り出し、順番を考慮しないで列挙します。
comination メソッドを使います。引数に取り出す数(M)を与えます。
instance method Array#combination
例: 巨人、中日、阪神、横浜、東京ヤクルト、広島の6チームから試合を行うときの組み合わせ
$ irb
> %w(巨人 中日 阪神 横浜 東京ヤクルト 広島).combination(2).to_a
=> [["巨人", "中日"], ["巨人", "阪神"], ["巨人", "横浜"], ["巨人", "東京ヤクルト"], [" 巨人", "広島"], ["中日", "阪神"], ["中日", "横浜"], ["中日", "東京ヤクルト"], ["中日", "広島"], ["阪神", "横浜"], ["阪神", "東京ヤクルト"], ["阪神", "広島"], ["横浜", "東京ヤクルト"], ["横浜", "広島"], ["東京ヤクルト", "広島"]]
順列(permutation)
N個の要素からM個を取り出して、順番を考慮して列挙します。
permutationメソッドを使います。引数に取り出す数(M)を与えます。
instance method Array#permutation
例: 巨人、中日、阪神、横浜、東京ヤクルト、広島の6チームから試合を行うときの組み合わせ(ホームチームを先にする)
$ irb
> %w(巨人 中日 阪神 横浜 東京ヤクルト 広島).permutation(2).to_a
=> [["巨人", "中日"], ["巨人", "阪神"], ["巨人", "横浜"], ["巨人", "東京ヤクルト"], [" 巨人", "広島"], ["中日", "巨人"], ["中日", "阪神"], ["中日", "横浜"], ["中日", "東京ヤクルト"], ["中日", "広島"], ["阪神", "巨人"], ["阪神", "中日"], ["阪神", "横浜"], ["阪神", "東京ヤクルト"], ["阪神", "広島"], ["横浜", "巨人"], ["横浜", "中日"], ["横浜", "阪神"], ["横浜", "東京ヤクルト"], ["横浜", "広島"], ["東京ヤクルト", "巨人"], ["東京ヤクルト", "中日"], ["東京ヤクルト", "阪神"], ["東京ヤクルト", "横浜"], ["東京ヤクルト", "広島"], ["広島", "巨人"], ["広島", "中日"], ["広島", "阪神"], ["広島", "横浜"], ["広島", "東京ヤクルト"]]
重複組み合わせ(repeated_combination)・重複順列(repeated_permutation)
N個の要素からM個を取り出すとき、重複を許し(同じものを選んでもよい)て組み合わせまたは順列を求めます。
instance method Array#repeated_combination
instance method Array#repeated_permutation
重複組み合わせや順列は、NやMの数が大きくなると膨大になるので注意。