torinaブログ

DjangoとBootstrap4で作成したブログ
Python, Django, Kivy, Bootstrap, Apache等のメモです
ソースコード

Pythonで、リストの内の要素の組み合わせ(順列)を列挙する

Python Python標準ライブラリ
約108日前 2016年11月10日19:19
例えば以下のようなリストがあったとします。
['a', 'b', 'c']


上のリストから、以下のような結果が得たいとします。
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')


このような場合、itertoolsのpermutationsを使うと楽ちんです。
これは順列を連続的に返します。
import itertools

for i in itertools.permutations(['a', 'b', 'c']):
    print(i)


結果
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')


range()等を渡すのも面白いです。
import itertools

for i in itertools.permutations(range(3)):  # 0, 1, 2
    print(i)


結果
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)



rという引数があり、これを指定することで生成する順列の長さを変えることができます。
import itertools

for i in itertools.permutations(['a', 'b', 'c'], r=2):
    print(i)


結果
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')



もし以下のように列挙したいならば...
('a',)
('b',)
('c',)
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')


以下のようにします。
import itertools

origin_list = ['a', 'b', 'c']
for i, _ in enumerate(origin_list, 1):     
    for j in itertools.permutations(origin_list, r=i):  # rには1、2、3と渡される
        print(j)


以下のコードは、今回は同じ動きをします。
enumerateを使うとインデックスと要素が渡されますが、要素は今回使わないので_としました。これはよく見る書き方です。
# enumerateを使う
for i, _ in enumerate(origin_list, 1):     

# 素直にやる
for i in range(1, len(origin_list)+1):  


origin_listにはリストが渡される前提です。
しかし、ジェネレータオブジェクトなどのステートフルな物が返されるとどうでしょうか。
import itertools


def create_gen(string):
    for char in string:
        yield char

origin_list = create_gen('123')
for i, _ in enumerate(origin_list, 1):
    for j in itertools.permutations(origin_list, r=i):  # rには1、2、3と渡される
        print(j)


結果。うまくいきません。
('2',)
('3',)


以下の2箇所でorigin_listに対してそれぞれnext()が呼ばれるのが原因です。
for i, _ in enumerate(origin_list, 1):
for j in itertools.permutations(origin_list, r=i):


create_genが自分で定義したものなら変更できますが、他のライブラリ等の容易に変更できない場合もあります。
そのような場合、複数回反復したいならば手っ取り早いのは、list()でリストにしてしまうことです。
import itertools


def create_gen(string):
    for char in string:
        yield char

# list()でリストにする
origin_list = list(create_gen('123'))
for i, _ in enumerate(origin_list, 1):
    for j in itertools.permutations(origin_list, r=i):  # rには1、2、3と渡される
        print(j)


問題なく動きます。
大量の要素があった場合にメモリ的に不安が残りますが、基本的には大丈夫でしょう。
また、sum()関数も同様のことが起きるので、覚えておきます。
('1',)
('2',)
('3',)
('1', '2')
('1', '3')
('2', '1')
('2', '3')
('3', '1')
('3', '2')
('1', '2', '3')
('1', '3', '2')
('2', '1', '3')
('2', '3', '1')
('3', '1', '2')
('3', '2', '1')


リストやセット等のコンテナ、複数回反復できるオブジェクトしか受け取りたくない!
という場合は以下のように判断できます。
import itertools


def create_gen(string):
    for char in string:
        yield char


origin_list = create_gen('123')
if iter(origin_list) is not iter(origin_list):
    for i, _ in enumerate(origin_list, 1):
        for j in itertools.permutations(origin_list, r=i):  # rには1、2、3と渡される
            print(j)


以下の部分で判断しています。iter()でselfを返してくるオブジェクトは、基本的に複数回の反復ができません。
if iter(origin_list) is not iter(origin_list):


以下のように書き換えると、問題なく動作します。
origin_list = ['a', 'b', 'c']



permutationsと似たもので、productというものもあります。
これはデカルト積を返しますが、サンプルを見るとわかりやすいです。
import itertools

origin_list = ['a', 'b', 'c']
for i in itertools.product(origin_list, repeat=3):
    print(i)


('a', 'a', 'a')
('a', 'a', 'b')
('a', 'a', 'c')
('a', 'b', 'a')
('a', 'b', 'b')
('a', 'b', 'c')
('a', 'c', 'a')
('a', 'c', 'b')
('a', 'c', 'c')
('b', 'a', 'a')
('b', 'a', 'b')
('b', 'a', 'c')
('b', 'b', 'a')
('b', 'b', 'b')
('b', 'b', 'c')
('b', 'c', 'a')
('b', 'c', 'b')
('b', 'c', 'c')
('c', 'a', 'a')
('c', 'a', 'b')
('c', 'a', 'c')
('c', 'b', 'a')
('c', 'b', 'b')
('c', 'b', 'c')
('c', 'c', 'a')
('c', 'c', 'b')
('c', 'c', 'c')


よくある、サイコロ2つの全ての組み合わせなんかは以下のようになります。
import itertools

origin_list = range(1, 7)  # 1から6
for i in itertools.product(origin_list, repeat=2):
    print(i)


(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(1, 6)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(2, 6)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(3, 5)
(3, 6)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(4, 5)
(4, 6)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
(5, 5)
(5, 6)
(6, 1)
(6, 2)
(6, 3)
(6, 4)
(6, 5)
(6, 6)


今回と似たようなものなら、combinations() やcombinations_with_replacement()等もあります。