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

Как насчет

np.unique(itertools.permutations([1, 1, 1]))

Проблема заключается в том, что теперь перестановки представляют собой строки массива Numpy, тем самым используя больше памяти, но вы можете циклически их перемещать по-прежнему

perms = np.unique(itertools.permutations([1, 1, 1]))
for p in perms:
    print p

В этом вопросе, когда я что-то искал сам!

Вот что я сделал:

def dont_repeat(x=[0,1,1,2]): # Pass a list
    from itertools import permutations as per
    uniq_set = set()
    for byt_grp in per(x, 4):
        if byt_grp not in uniq_set:
            yield byt_grp
            uniq_set.update([byt_grp])
    print uniq_set

for i in dont_repeat(): print i
(0, 1, 1, 2)
(0, 1, 2, 1)
(0, 2, 1, 1)
(1, 0, 1, 2)
(1, 0, 2, 1)
(1, 1, 0, 2)
(1, 1, 2, 0)
(1, 2, 0, 1)
(1, 2, 1, 0)
(2, 0, 1, 1)
(2, 1, 0, 1)
(2, 1, 1, 0)
set([(0, 1, 1, 2), (1, 0, 1, 2), (2, 1, 0, 1), (1, 2, 0, 1), (0, 1, 2, 1), (0, 2, 1, 1), (1, 1, 2, 0), (1, 2, 1, 0), (2, 1, 1, 0), (1, 0, 2, 1), (2, 0, 1, 1), (1, 1, 0, 2)])

В принципе, создайте набор и продолжайте добавлять к нему. Лучше, чем создавать списки и т. Д., Которые занимают слишком много памяти. Надеюсь, это поможет следующему человеку, смотрящему :-) Комментируйте набор «обновление» в функции, чтобы увидеть разницу.

Поскольку иногда новые вопросы отмечены как дубликаты, и их авторы ссылаются на этот вопрос, может быть важно упомянуть, что для этой цели у sympy есть итератор.

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Наступил другой день, когда я работал над собственной проблемой. Мне нравится подход Луки Ране, но я думал, что использование класса Counter в библиотеке коллекций показалось скромным. Вот мой код:

def unique_permutations(elements):
    "Returns a list of lists; each sublist is a unique permutations of elements."
    ctr = collections.Counter(elements)

    # Base case with one element: just return the element
    if len(ctr.keys())==1 and ctr[ctr.keys()[0]] == 1:
        return [[ctr.keys()[0]]]

    perms = []

    # For each counter key, find the unique permutations of the set with
    # one member of that key removed, and append the key to the front of
    # each of those permutations.
    for k in ctr.keys():
        ctr_k = ctr.copy()
        ctr_k[k] -= 1
        if ctr_k[k]==0: 
            ctr_k.pop(k)
        perms_k = [[k] + p for p in unique_permutations(ctr_k)]
        perms.extend(perms_k)

    return perms

Этот код возвращает каждую перестановку в виде списка. Если вы будете кормить его строкой, она даст вам список перестановок, где каждый из них представляет собой список символов. Если вы хотите, чтобы результат был как список строк (например, если вы ужасный человек, и вы хотите злоупотреблять моим кодом, чтобы помочь вам обмануть Scrabble), просто выполните следующие действия:

[''.join(perm) for perm in unique_permutations('abunchofletters')]

Звучит так, как будто вы ищете itertools.combinations () docs.python.org

list(itertools.combinations([1, 1, 1],3))
[(1, 1, 1)]

Это мое решение с 10 строками:

class Solution(object):
    def permute_unique(self, nums):
        perms = [[]]
        for n in nums:
            new_perm = []
            for perm in perms:
                for i in range(len(perm) + 1):
                    new_perm.append(perm[:i] + [n] + perm[i:])
                    # handle duplication
                    if i < len(perm) and perm[i] == n: break
            perms = new_perm
        return perms


if __name__ == '__main__':
    s = Solution()
    print s.permute_unique([1, 1, 1])
    print s.permute_unique([1, 2, 1])
    print s.permute_unique([1, 2, 3])

--- Результат ----

[[1, 1, 1]]
[[1, 2, 1], [2, 1, 1], [1, 1, 2]]
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

Грубо так же быстро, как и ответ Луки Ране, но короче & amp; более простой, IMHO.

def unique_permutations(elements):
    if len(elements) == 1:
        yield (elements[0],)
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for sub_permutation in unique_permutations(remaining_elements):
                yield (first_element,) + sub_permutation

>>> list(unique_permutations((1,2,3,1)))
[(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ... , (3, 1, 2, 1), (3, 2, 1, 1)]

Он работает рекурсивно, устанавливая первый элемент (итерируя через все уникальные элементы) и повторяя через перестановки для всех остальных элементов.

Давайте пройдем unique_permutations of (1,2,3,1), чтобы увидеть, как он работает:

• unique_elements - 1,2,3
• Пропустим через них : first_element начинается с 1. remaining_elements - [2,3,1] (т. е. 1,2,3,1 минус первый 1). Мы перебираем (рекурсивно) через перестановки остальных элементов: (1, (3, 1, 2), (3, 2, 1). Для каждого sub_permutation мы вставляем first_element: (1,1,2,3), (1,1,3,2), ... и получаем результат.
• Теперь мы переходим к first_element = 2 и делаем то же, что и выше. remaining_elements - [1,3,1] (т. е. 1,2,3,1 минус первые 2). Мы перебираем через перестановки остальных элементов: (1, 1, 3), (1, 3, 1 ), (3, 1, 1) Для каждого sub_permutation вставляем first_element: (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1 ) ... и дать результат.
• Наконец, мы делаем то же самое с first_element = 3.

Я придумал очень подходящую реализацию, используя itertools.product в этом случае (это реализация, где вы хотите все комбинации

unique_perm_list = [''.join(p) for p in itertools.product(['0', '1'], repeat = X) if ''.join(p).count() == somenumber]

, это по существу комбинация (n над k) с n = X и somenumber = k itertools.product () итерации от k = 0 до k = X, последующая фильтрация с подсчетом гарантирует, что в список будут внесены только перестановки с правильным количеством единиц. Вы можете легко увидеть, что это работает, когда вы вычислить n над k и сравнить его с len (unique_perm_list)

Вы можете попробовать использовать set:

>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 1)]

Вызов для установки удаленных дубликатов

Здесь рекурсивное решение проблемы.

def permutation(num_array):
    res=[]
    if len(num_array) <= 1:
        return [num_array]
    for num in set(num_array):
        temp_array = num_array.copy()
        temp_array.remove(num)
        res += [[num] + perm for perm in permutation(temp_array)]
    return res

arr=[1,2,2]
print(permutation(arr))

Наивный подход может заключаться в том, чтобы взять набор перестановок:

list(set(it.permutations([1, 1, 1])))
# [(1, 1, 1)]

Однако этот метод расточительно вычисляет репликативные перестановки и отбрасывает их. Более эффективным подходом будет more_itertools.distinct_permutations , сторонний инструмент .

Код

import itertools as it

import more_itertools as mit


list(mit.distinct_permutations([1, 1, 1]))
# [(1, 1, 1)]

Производительность

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

iterable = [1, 1, 1, 1, 1, 1]
len(list(it.permutations(iterable)))
# 720

%timeit -n 10000 list(set(it.permutations(iterable)))
# 10000 loops, best of 3: 111 µs per loop

%timeit -n 10000 list(mit.distinct_permutations(iterable))
# 10000 loops, best of 3: 16.7 µs per loop

Мы видим, что more_itertools.distinct_permutations на порядок быстрее.

Подробности

Из исходного кода алгоритм рекурсии (как показано в принятом ответе) используется для вычисления различных перестановок, тем самым устраняя расточительные вычисления. Подробнее см. Исходный код .

Это полагается на деталь реализации, что любая перестановка отсортированного итерабельного в отсортированном порядке, если они не являются дубликатами предшествующих перестановок.

from itertools import permutations

def unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p
            yield p

for p in unique_permutations('cabcab', 2):
    print p

дает

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