～ 順列全探索 ～ チートシート

目次

まずは使用するライブラリをインポート import itertools

全組み合わせを列挙　list(itertools.permutations(mat))
全組み合わせをfor文で処理　for per in itertools.permutations(mat):

はじめに

チートシートの扱いついてはここを読んでください

全組み合わせを列挙

permutations.py

import itertools

mat = [1, 2, 3, 4]

per = list(itertools.permutations(mat))
print(per)

mat

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

第２引数を指定しない場合は、すべての要素を並べ変えてできる組み合わせとなる。（nCn）

permutations.py

import itertools

mat = [1, 2, 3, 4]

per = list(itertools.permutations(mat, 2))
print(per)

mat

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

第２引数を指定すると、指定した数の要素を選び並べ変えてできる組み合わせとなる。(nCk)

全組み合わせをfor文で処理

permutations.py

import itertools

mat = [1, 2, 3, 4]
for per in itertools.permutations(mat):
  print(list(per))

mat

>>> [1, 2, 3, 4]
>>> [1, 2, 4, 3]
>>> [1, 3, 2, 4]
>>> [1, 3, 4, 2]
>>> [1, 4, 2, 3]
>>> [1, 4, 3, 2]
 :

list()で配列化する
愚直にfor文で頑張って順列全探索を実装しても速度で勝てないので、itertoolsを使ってスマートに実装

permutations.py

import itertools

mat = [1, 2, 3, 4]
for per in itertools.permutations(mat, 2):
  print(list(per))

mat

>>> [1, 2]
>>> [1, 3]
>>> [1, 4]
>>> [2, 1]
>>> [2, 3]
>>> [2, 4]
 :

第２引数で要素数を指定