Pythonのitertoolsで順列や組合せを重複あり・なしで全列挙する

順列や組合せを求めたいときに、ネストしたループを組むと可読性が低いしネストの回数が変わるとコードの保守も面倒くさい。

itertoolsを使えば、読みやすいコードで全列挙を簡単にしてくれる。

itertools --- 効率的なループ用のイテレータ生成関数群
このモジュールは イテレータ を構築する部品を実装しています。プログラム言語 APL, Haskell, SML からアイデアを得ていますが、 Python に適した形に修正されています。 このモジュールは、高速でメモリ効率に優れ、単独でも...

組合せイテレータは全部で4種類。

abcという文字列から2個選ぶケースを試してみる。

順列・重複あり

import itertools

all = itertools.product('abc', repeat=2)
for x in all:
    print(x)


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

順列・重複なし

import itertools

all = itertools.permutations('abc', 2)
for x in all:
    print(x)


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

組合せ・重複あり

import itertools

all = itertools.combinations_with_replacement('abc', 2)
for x in all:
    print(x)


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

組合せ・重複なし

import itertools

all = itertools.combinations('abc', 2)
for x in all:
    print(x)


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

試しにitertoolsでAtCoder Beginner Contest 029 C – Brute-force Attackを解いてみる。

C - Brute-force Attack
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

import itertools

n = int(input())

ans = itertools.product('abc', repeat=n)
for l in ans:
    print(''.join(l))

これで全列挙する時の選択肢を増やすことができた。

コメント

タイトルとURLをコピーしました