同じものを含む順列の列挙

itertools.permutations は同じ値も区別して並べるので、たとえば $0, 0, 1$ からは同じ並びが 2 回ずつ出てきます。ここでは C++ の next_permutation と同じ方法で、辞書順で次の並びに直接進むことで、同じ並びは 1 回だけ出します。全部作ってから set に入れるのと違い、出てくる並びの個数に比例する時間で済みます。並びの個数は 二項係数 の multinomial で数えられます。

要素は大小を比べられるもの（数や文字列など）とします。

• multiset_permutations(a, r): a から $r$ 個（省略すると全部）選んで並べたタプルを、同じものは 1 回だけ、辞書順に返すジェネレータ。sorted(set(permutations(a, r))) と同じものが順に出てくる。1 個あたり $O(N)$
• next_permutation(a): リスト a をその場で辞書順の次の並びに書き換えて True を返す。最後の並びだったときは書き換えずに False を返す。 $O(N)$

例:

for p in multiset_permutations([0, 0, 1, 2]):
    print(*p)
# 0 0 1 2
# 0 0 2 1
# 0 1 0 2
# ...（全部で 4! / 2! = 12 通り）

コード

def next_permutation(a):
    # a を辞書順で次の並びに書き換える（同じ値があっても、同じ並びは飛ばす）。最後の並びなら False
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i < 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = a[i + 1:][::-1]
    return True


def multiset_permutations(a, r=None):
    # a から r 個（省略すると全部）選んで並べたものを、同じ並びは 1 回だけ、辞書順に列挙する
    a = sorted(a)
    n = len(a)
    if r is None:
        r = n
    if r > n:
        return
    while True:
        yield tuple(a[:r])
        a[r:] = a[r:][::-1]  # 残りを降順にして、先頭 r 個が次の並びに進むようにする
        if not next_permutation(a):
            return