この記事では、Pythonで「順列(Permutation)」と「組み合わせ(Combination)」を計算する方法を解説します。
「順列」と「組み合わせ」とは、異なるn個のものからr個を取り出すことを言います。ただし、順列は並べる順序を考慮しますが、組み合わせは順序を無視して取り出し方のみを考慮します。
ついでに、「重複組み合わせ」と「デカルト積」についても見ていきましょう！
順列とは、互いに異なるn個のものからr個取り出してそれを１列に並べるとき、その並べ方をn個のものからr個取ることです。
例えば「A・B・C」の中から2こ取り出すときの順列は以下のようになります。
「AB・AC・BA・BC・CA・CB」の 6通り。
順列の総数を取得するには、mathモジュールのperm()関数を使います。
※ Python 3.8で追加
import math math.perm(n, k=None)n個の中からk個取り出したときの順列の総数を返します。k > nの場合、0が返されます。
import math print(math.perm(3, 2))実行結果
6kを指定しないか、Noneの場合、k = nとなる。
import math # math.perm(3, 3)と同じ print(math.perm(3))実行結果
6引数が整数でない場合はTypeError、負の場合はValueErrorが発生します。
itertoolsモジュールのpermutations()関数を使うことでイテラブルから順列を生成することができます。
import itertools itertools.permutations(iterable, r=None)iterable引数からr個取り出す順列のイテレータを返します。
import itertools n = ['A', 'B', 'C'] p = itertools.permutations(n, 2) for v in p: print(v)実行結果
('A', 'B') ('A', 'C') ('B', 'A') ('B', 'C') ('C', 'A') ('C', 'B')r引数を省略すると指定されたiterable引数の長さが渡される。
import itertools n = ['A', 'B', 'C'] # itertools.permutations(n, 3)と同じ p = itertools.permutations(n) for v in p: print(v)実行結果
('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')組み合わせとは、互いに異なるn個のものからr個取り出して組み合わせることです。順列と異なる点は、並べる順序は問題にしない点です。
例えば「A・B・C」の中から2こ取り出すときの組み合わせは以下のようになります。
「AB・AC・BC」の3通りです。
BA・CA・CBは、順序が異なるだけなので組み合わせでは考慮しません。
組み合わせの総数を取得するには、mathモジュールのcomb()関数を使います。
※ Python 3.8で追加
import math math.comb(n, k)n個の中からk個取り出したときの組み合わせの総数を返します。k > nの場合、0が返されます。順列の関数とは異なりk引数を省略することはできません。
import math print(math.comb(3, 2))実行結果
3引数が整数でない場合はTypeError、負の場合は ValueErrorが発生します。
itertoolsモジュールのcombinations()関数を使うことでイテラブルから組み合わせを生成することができます。
import itertools itertools.combinations(iterable, r)iterable引数からr個取り出す組み合わせのイテレータを返します。
import itertools n = ['A', 'B', 'C'] c = itertools.combinations(n, 2) for v in c: print(v)実行結果
('A', 'B') ('A', 'C') ('B', 'C')順列と異なりr引数を省略できないことに注意。
重複組み合わせとは、重複する元も組にする組み合わせです。
例えば「A・B・C」の中から2こ取り出すときの重複組み合わせは以下のようになります。
「AA・AB・AC・BB・BC・CC」の6通りです。
重複組み合わせの総数を取得できる関数は用意されていないので自作関数を作成する必要がある。以下のようにcomb関数を使うことで求めることができる。
import math def combr(n, r): return math.comb(n + r - 1, r) print(combr(3, 2))実行結果
6itertoolsモジュールのcombinations_with_replacement()関数を使うことでイテラブルから重複組み合わせを生成することができます。
import itertools itertools.combinations_with_replacement(iterable, r)iterable引数からr個取り出す組み合わせのイテレータを返します。
import itertools cr = itertools.combinations_with_replacement('ABC', 2) for v in cr: print(v)実行結果
('A', 'A') ('A', 'B') ('A', 'C') ('B', 'B') ('B', 'C') ('C', 'C')r引数は省略できません。
デカルト積とは、複数の集合から1つずつ要素を取り出して組にしたものを持った集合です。
例えば「A・B・C」と「X・Y・Z」のデカルト積は以下のようになります。
「AX・AY・AZ・BX・BY・BZ・CX・CY・CZ」の9通りです。
デカルト積の総数は、集合の長さの積で求めることができます。mathモジュールのprod()関数に集合の長さを渡すことで求めることができます。
import math import itertools abc = ['A', 'B', 'C'] xyz = ['X', 'Y', 'Z'] lengths = (len(abc), len(xyz)) print(math.prod(lengths))実行結果
9itertoolsモジュールのproduct()関数を使うことでイテラブルからデカルト積を生成することができます。
import itertools itertools.product(*iterables, repeat=1)iterables引数のデカルト積をイテレータとして返します。
import itertools n = ['A', 'B', 'C'] m = ['X', 'Y', 'Z'] p = itertools.product(n, m) for v in p: print(v)実行結果
('A', 'X') ('A', 'Y') ('A', 'Z') ('B', 'X') ('B', 'Y') ('B', 'Z') ('C', 'X') ('C', 'Y') ('C', 'Z')repeat引数を指定することでiterables自身とのデカルト積を求めることができます。
import itertools # product(['A', 'B', 'C'], ['A', 'B', 'C'])と等価 p = itertools.product(['A', 'B', 'C'], repeat=2) for v in p: print(v)実行結果
('A', 'A') ('A', 'B') ('A', 'C') ('B', 'A') ('B', 'B') ('B', 'C') ('C', 'A') ('C', 'B') ('C', 'C')for文を2つ重ねたジェネレータ式で同等のものを生成することができます。
abc = 'abc' xyz = 'xyz' # for文を2つ重ねたジェネレータ式 p = ((x,y) for x in abc for y in xyz) for v in p: print(v)実行結果
('a', 'x') ('a', 'y') ('a', 'z') ('b', 'x') ('b', 'y') ('b', 'z') ('c', 'x') ('c', 'y') ('c', 'z')この記事では、Pythonで順列(Permutation)と組み合わせ(Combination)を計算する方法を解説しました。
Pythonでは、あらかじめモジュールに用意されているので簡単に計算できました。
それでは今回の内容はここまでです。ではまたどこかで〜( ・∀・)ﾉ
View Comments