Создание перестановок списка с повторяющимися элементами

В Python довольно просто создать все перестановки списка, используя модуль itertools. У меня есть ситуация, когда список, который я использую, имеет только два символа (т.е. "1122" ). Я хочу сгенерировать все уникальные перестановки.

Для строки "1122" существует 6 уникальных перестановок (1122, 1212, 1221 и т.д.), но itertools.permutations даст 24 элемента. Это просто, чтобы записывать уникальные перестановки, но для их сбора потребуется гораздо больше времени, чем необходимо, поскольку все 720 элементов считаются.

Есть ли функция или модуль, который учитывает повторяющиеся элементы при генерации перестановок, поэтому мне не нужно писать свои собственные?

Ответ 1

Эта веб-страница выглядит многообещающей.

def next_permutation(seq, pred=cmp):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""
    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    if not seq:
        raise StopIteration
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
    first = 0
    last = len(seq)
    seq = seq[:]
    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq[:]
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            # Step 1.
            next1 = next
            next -= 1
            if pred(seq[next], seq[next1]) < 0:
                # Step 2.
                mid = last - 1
                while not (pred(seq[next], seq[mid]) < 0):
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                # Step 3.
                reverse(seq, next1, last)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

>>> for p in next_permutation([int(c) for c in "111222"]):
...     print p
... 
[1, 1, 1, 2, 2, 2]
[1, 1, 2, 1, 2, 2]
[1, 1, 2, 2, 1, 2]
[1, 1, 2, 2, 2, 1]
[1, 2, 1, 1, 2, 2]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 2, 1]
[1, 2, 2, 1, 1, 2]
[1, 2, 2, 1, 2, 1]
[1, 2, 2, 2, 1, 1]
[2, 1, 1, 1, 2, 2]
[2, 1, 1, 2, 1, 2]
[2, 1, 1, 2, 2, 1]
[2, 1, 2, 1, 1, 2]
[2, 1, 2, 1, 2, 1]
[2, 1, 2, 2, 1, 1]
[2, 2, 1, 1, 1, 2]
[2, 2, 1, 1, 2, 1]
[2, 2, 1, 2, 1, 1]
[2, 2, 2, 1, 1, 1]
>>>

2017-08-12

Семь лет спустя, вот лучший алгоритм (лучше для ясности):

from itertools import permutations

def unique_perms(series):
    return {"".join(p) for p in permutations(series)}

print(sorted(unique_perms('1122')))

Ответ 2

Использование множества упрощает решение. Струны с повторяющимися символами и не повторяется, используется в качестве входных данных.

import re
from itertools import permutations

def perm(s):
    l = re.split('\B',s)
    return set(list(permutations(l,len(l))))

    l = '1122'

    perm(l)

    {('1', '1', '2', '2'),
     ('1', '2', '1', '2'),
     ('1', '2', '2', '1'),
     ('2', '1', '1', '2'),
     ('2', '1', '2', '1'),
     ('2', '2', '1', '1')}


    l2 = '1234'

    perm(l2)

    {('1', '2', '3', '4'),
     ('1', '2', '4', '3'),
     ('1', '3', '2', '4'),
     ('1', '3', '4', '2'),
     ('1', '4', '2', '3'),
     ('1', '4', '3', '2'),
     ('2', '1', '3', '4'),
     ('2', '1', '4', '3'),
     ('2', '3', '1', '4'),
     ('2', '3', '4', '1'),
     ('2', '4', '1', '3'),
     ('2', '4', '3', '1'),
     ('3', '1', '2', '4'),
     ('3', '1', '4', '2'),
     ('3', '2', '1', '4'),
     ('3', '2', '4', '1'),
     ('3', '4', '1', '2'),
     ('3', '4', '2', '1'),
     ('4', '1', '2', '3'),
     ('4', '1', '3', '2'),
     ('4', '2', '1', '3'),
     ('4', '2', '3', '1'),
     ('4', '3', '1', '2'),
     ('4', '3', '2', '1')}

Ответ 3

more-itertools.distinct_permutations(iterable)

Получает последовательные различные перестановки элементов в итерируемых.

Эквивалентен set(permutations(iterable)), за исключением того, что дубликаты не генерируется и выбрасывается. Для больших входных последовательностей, это много более эффективный.

from more_itertools import distinct_permutations

for p in distinct_permutations('1122'):
    print(''.join(p))

# 2211
# 2121
# 1221
# 2112
# 1212
# 1122

Установка:

pip install more-itertools