Posted at

[python] 同じ要素を考慮した順列の生成

More than 3 years have passed since last update.


同じ要素を含む順列の生成

itertools.permutationsだと、同じ要素のとき、余分に生成される。

同じ数字、同じ文字、同順、等扱うとき使います。

前にジェネレータの使い方で紹介したが、自分が探しにくかったので単体で紹介。

github source: permutation.py


permutation.py

def permutations(iterable, permutation=[]):

if not iterable:
yield permutation
pass
for i in [iterable.index(i) for i in set(iterable)]:
yield from permutations(iterable[:i] + iterable[i+1:], permutation + [iterable[i]])

yield from は再帰的?に、yieldを遠くから返してくれます。

毎回setして、同じ要素の重複を防いでいます。

スライスでくっつけるの若干遅そうなので、うまいやり方あれば教えて欲しいです。