「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

https://ref.xaio.jp/ruby/classes/array/repeated_combination

https://ref.xaio.jp/ruby/classes/array/repeated_combination