перестановки с уникальными значениями

Это зависит от деталей реализации, что любая перестановка в отсортированном массиве упорядочены, если они являются дубликатами до перестановок.

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')

поскольку иногда новые вопросы помечаются как дубликаты и их авторы ссылаются на этот вопрос, может быть важно упомянуть, что 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]]

примерно так же быстро, как ответ Луки ране, но короче и проще, ИМХО.

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 из (1,2,3,1), чтобы увидеть, как это работает:

• unique_elements являются 1,2,3
• давайте переберем их:first_element начинается с 1.
  • remaining_elements это [2,3,1] (т. е. 1,2,3,1 минус первый 1)
  • перебирать (рекурсивно) путем перестановок остальных элементов: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 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.

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

>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 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]]

это звучит так, как будто вы ищете itertools.комбинации() docs.python.org

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

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

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

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

код

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 на порядок быстрее.

---

подробности

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

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

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

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)])

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

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

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))

а как же

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

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

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

наткнулся на это на днях, работая над своей собственной проблемой. Мне нравится подход Луки ране, но я думал, что использование класса 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.продукт в этом случае (это реализация, где вы хотите все комбинации

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.продукт () повторяется от k = 0 до k = X последующая фильтрация с подсчетом гарантирует, что только перестановки с правильным числом единиц будут приведены в список. вы можете легко увидеть, что это работает, когда вы вычисляете n над k и сравниваете его в len (unique_perm_list)