Pythonのitertoolsを使って文字列の重複しない順列を先頭からn個出力する方法

順列（パーミュテーション）とは、複数のオブジェクトを異なる並び順で表現したものです。しかし、与えられたオブジェクトの中に同じ要素が含まれている場合、生成される順列の中にまったく同じ並びが現れることがあります。この記事では、Pythonの標準ライブラリitertoolsを使って、重複を除いた一意な順列だけを効率よく取り出す方法を解説します。

基本の考え方

itertoolsモジュールには、順列を生成するためのpermutations()メソッドが用意されています。ただし、元の文字列に重複した文字が含まれていると、このメソッドは同一の並びを何度も返してしまいます。

そこで、以下の手順で一意な順列のみを取得します。

• sorted()メソッドで文字をあらかじめソートしておくことで、順列を辞書順に近い形で生成できるようにします。
• set（集合）を利用して、すでに出力済みの順列を記録し、重複する並びを自動的に除外します。

サンプルコード

次のプログラムでは、変数kが「全ての一意な順列の中から表示したい最大件数」を表しています。whileループの中で、まだ集合に登録されていない順列だけを最終的なリストに追加していきます。

from itertools import permutations
def permutation_value(str, k):
    s = sorted(list(str))
    p = permutations(s)
    m = 0
    set_1 = set()
    str = ''
    while m < k:
        str = ''.join(p.__next__())
        if str not in set_1:
            set_1.add(str)
            print(str)
            m += 1
str = "xyxxz"
i = 12
permutation_value(str, i)

実行結果

上記のコードを実行すると、次のような出力が得られます。

xxxyz
xxxzy
xxyxz
xxyzx
xxzxy
xxzyx
xyxxz
xyxzx
xyzxx
xzxxy
xzxyx
xzyxx

コードのポイント

• sorted(list(str))により、文字列「xyxxz」の各文字がソートされ、「xxxyz」という状態から順列の生成が始まります。これにより、出力が辞書順に近い順序になります。
• p.__next__()でイテレータから順に1つずつ順列を取り出し、''.join()でタプルを文字列に変換しています。
• 集合set_1への登録状況を確認することで、同じ並びの順列がカウントmに影響しないよう制御しています。

なお、より実践的にはnext(p)を使うか、dict.fromkeys()やsetとの組み合わせで重複除去を行う方法も一般的です。文字数が多い場合は順列の総数が爆発的に増えるため、必要な件数だけを取得するこの手法は計算量の面でも有効です。