2014/12/10

Python Tips:順列や組み合わせを作りたい

Pythonで、数学でいう nPr や nCr 、いわゆる「順列」や「組み合わせ」を作る方法をご紹介します。

結論としては itertools ライブラリを使う方法がかんたんです。

以下、順番に見ていきます。
  1. 順列
  2. 組み合わせ


順列

itertools.permutations を使います。
from itertools import permutations

original = "abc"
permutations(original)
# => [('a', 'b', 'c'),
      ('a', 'c', 'b'),
      ('b', 'a', 'c'),
      ('b', 'c', 'a'),
      ('c', 'a', 'b'),
      ('c', 'b', 'a')]
引数には、要素を格納したリストなどを渡します。

int を第2引数として与えると長さを指定することもできます。
permutations(original, 2)
# => [('a', 'b'), 
      ('a', 'c'), 
      ('b', 'a'), 
      ('b', 'c'), 
      ('c', 'a'), 
      ('c', 'b')]

順列は英語で permutations なので、名前そのままですね。


組み合わせ

こちらは itertools.combinations を使います。

こちらも組み合わせの英語にあたる「combination」と、そのままの名前になっています。
from itertools import combinations

original = "abc"
combinations(original, 2)
# => [('a', 'b'), ('a', 'c'), ('b', 'c')]
こちらも、第1引数にリストなどの iterable な要素を、第2引数に int を渡します。

こちらは permutations と異なり、第2引数が必須となっています。


以上です。


参考
9.7. itertools — Functions creating iterators for efficient looping — Python公式ドキュメント
algorithm - How to generate all permutations of a list in Python - Stack Overflow
Python code to pick out all possible combinations from a list? - Stack Overflow

0 件のコメント: