「permutation」「combination」メソッドによる順列/組み合わせの数え上げ
【結論】
・permutation
メソッドは、配列から引数n個の要素を選んだときの順列を数え上げる。
・combination
メソッドは、配列から引数n個の要素を選んだときの組合せを数え上げる。
・要素の重複を許可する場合はrepeated_combination
メソッド(repeated_permutation
メソッド )を利用する。
【目次】
【本題】
順列と組み合わせの違い
Rubyには、配列から順列・組み合わせと数え上げるメソッドが存在します。
それらの解説の前に、それぞれの違いについて説明します。
「順列」「組み合わせ」は、以下の様に定義されています。
・順列 n個の中から、r個を順番に取り出して並べる総数。
・組み合わせ n個の集合の中からm個を取り出す組合せ
これだけだと分かりづらいですが、簡単に言うと「順序違いによる重複を許可するか?しないか?」の違いです。
例えば「1・2・3・4・5」の5枚のカードがあるとします。
この5枚のカードについて、2種類の問題を出します。
1:「このカードから2枚を選び、2ケタの数字を作る場合、作れる数字は何通りあるか?」 2:「このカードから2枚を選ぶ場合、選び方は何通りあるか?」
それぞれ同じ問題に見えますが、答えが異なります。
1の答えが「20通り」です。 2の答えが「10通り」です。
1の場合、「1・2」と「2・1」という順番が違うが組み合わせが同じ場合でも、数にカウントされます。 2の場合、「1・2」と「2・1」は、同じ組み合わせ(重複)と見なされて、片方が数にカウントされません。
その為、この様な違いが生まれています。
permutationメソッド
permutation
メソッドは、配列から引数n個の要素を選んだときの順列を数え上げます。
numbers = [1, 2, 3, 4, 5] numbers.permutation(2) {|a, b| printf("(%d, %d) ", a, b) } => (1, 2) (1, 3) (1, 4) (1, 5) (2, 1) (2, 3) (2, 4) (2, 5) (3, 1) (3, 2) (3, 4) (3, 5) (4, 1) (4, 2) (4, 3) (4, 5) (5, 1) (5, 2) (5, 3) (5, 4)
combinationメソッド
combination
メソッドは、配列から引数n個の要素を選んだときの組合せを数え上げる。
numbers = [1, 2, 3, 4, 5] numbers.combination(2) {|a, b| printf("(%d, %d) ", a, b) } => (1, 2) (1, 3) (1, 4) (1, 5) (2, 3) (2, 4) (2, 5) (3, 4) (3, 5) (4, 5)
要素の重複
なお先ほどのメソッドだと、同じ要素の重複を許可していません。
要素の重複を許可する場合はrepeated_combination
メソッド(repeated_permutation
メソッド )を利用します。
numbers = [1, 2, 3, 4, 5] numbers.repeated_permutation(2) {|a, b| printf("(%d, %d) ", a, b) } => (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5)
numbers = [1, 2, 3, 4, 5] numbers.repeated_combination(2) {|a, b| printf("(%d, %d) ", a, b) } => (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 2) (2, 3) (2, 4) (2, 5) (3, 3) (3, 4) (3, 5) (4, 4) (4, 5) (5, 5)
参考情報
https://ref.xaio.jp/ruby/classes/array/permutation
https://ref.xaio.jp/ruby/classes/array/combination