BETA

初心者日記(17)『itertoolsで組み合わせ列挙』

投稿日:2020-07-17
最終更新:2020-07-17

例えば『1,2,3』の数字があり、これから重複可能で3つ選ぶとしたら、

1-1-1  
2-1-3  
3-1-1  

色々な組み合わせを考えられる。この場合は『3 * 3 * 3 = 27』通り。3重ループならfor文を回してこの組み合わせを考えるのもありだが、便利なライブラリを見つけた。

itertools、今回使うのは組み合わせイテレータのところ。

product

import itertools  

a = [1,2,3]  
l = list(itertools.product(a,repeat = 3))  
print(l)  
[(1, 1, 1), (1, 1, 2), (1, 1, 3),   
(1, 2, 1), (1, 2, 2), (1, 2, 3),   
(1, 3, 1), (1, 3, 2), (1, 3, 3),   
(2, 1, 1), (2, 1, 2), (2, 1, 3),   
(2, 2, 1), (2, 2, 2), (2, 2, 3),   
(2, 3, 1), (2, 3, 2), (2, 3, 3),   
(3, 1, 1), (3, 1, 2), (3, 1, 3),   
(3, 2, 1), (3, 2, 2), (3, 2, 3),   
(3, 3, 1), (3, 3, 2), (3, 3, 3)]  

productは全ての重複ありの組み合わせを探してくれる。長さはrepeatで決めれる。

permutations

import itertools  

a = [1,2,3]  
l = list(itertools.permutations(a,3))  
print(l)  
[(1, 2, 3), (1, 3, 2), (2, 1, 3),   
(2, 3, 1), (3, 1, 2), (3, 2, 1)]  

permutationsはproductの重複なしバージョン。

combinations

import itertools  

a = [1,2,3,4]  
l = list(itertools.combinations(a,3))  
print(l)  
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]  

combinationsは前から順番に重複なしで探してくれる。
1→2→3→4〇
4→3→2→1×

combinations_with_replacement

import itertools  

a = [1,2,3,4]  
l = list(itertools.combinations_with_replacement(a,3))  
print(l)  
[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4),   
(1, 2, 2), (1, 2, 3), (1, 2, 4),   
(1, 3, 3), (1, 3, 4), (1, 4, 4),   
(2, 2, 2), (2, 2, 3), (2, 2, 4),   
(2, 3, 3), (2, 3, 4), (2, 4, 4),   
(3, 3, 3), (3, 3, 4), (3, 4, 4), (4, 4, 4)]  

combinations_with_replacementはcombinationsの重複ありバージョン。

最近AtCoderで使う度に調べていたので自分用にまとめてみた。これでABC162 C - Sum of gcd of Tuples (Easy)が解けるはず!
...と思ってproductを使ったが最大条件の200で約4秒かかった。また考えないと。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

tnodino(つのでぃの)のブログ。日頃の内容を記事にしています。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう