【Python】itertoolsを使った順列・組み合わせの実装

順列・組み合わせの実装方法

pythonでは、itertoolsライブラリを使うことで順列・組み合わせを簡単に実装することができます。

重複ありの順列

同じ選択をできる場合の順列は、itertools.productを使うことで実装することができます。

2^N通りの順列を作りたい際に使用します。

import itertools

list(itertools.product([1, 2, 3, 4], repeat=2))

[(1, 1), (1, 2), (1, 3), (1, 4),
 (2, 1), (2, 2), (2, 3), (2, 4),
 (3, 1), (3, 2), (3, 3), (3, 4),
 (4, 1), (4, 2), (4, 3), (4, 4)]

重複なしの順列

同じ選択をできない場合の順列は、itertools.permutationsを使うことで実装することができます。

import itertools

list(itertools.permutations([1, 2, 3, 4], 2))

[(1, 2), (1, 3), (1, 4),
 (2, 1), (2, 3), (2, 4),
 (3, 1), (3, 2), (3, 4),
 (4, 1), (4, 2), (4, 3)]

重複ありの組み合わせ

同じ選択をできる場合の組み合わせは、itertools.combinations_with_replacementを使うことで実装することができます。

import itertools

list(itertools.combinations_with_replacement([1, 2, 3, 4], 2))

[(1, 1), (1, 2), (1, 3), (1, 4),
 (2, 2), (2, 3), (2, 4),
 (3, 3), (3, 4),
 (4, 4)]

重複なしの組み合わせ

同じ選択をできない場合の組み合わせは、itertools.combinationsを使うことで実装することができます。

import itertools

list(itertools.combinations([1, 2, 3, 4], 2))

[(1, 2), (1, 3), (1, 4), 
 (2, 3), (2, 4), 
 (3, 4)]

参考文献

itertools --- 効率的なループ用のイテレータ生成関数群

このモジュールは イテレータ を構築する部品を実装しています。プログラム言語 APL, Haskell, SML からアイデアを得ていますが、 Python に適した形に修正されています。 このモジュールは、高速でメモリ効率に優れ、単独でも組合せても使用することのできるツールを標準化したものです。同時に、このツール群は...

docs.python.org