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

Question

itertools.permutations генерирует, где его элементы рассматриваются как уникальные, основываясь на их положении, а не на их значении.В общем, я хочу избежать дубликатов, подобных этому:

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

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

Кто-нибудь знает подходящий алгоритм дляэто?

Большое спасибо!

РЕДАКТИРОВАТЬ:

Что я в основном хочу, это следующее:

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

что невозможно, потому что sorted создает список, а вывод itertools.product слишком велик.

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

Answer 1

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1




a = list(perm_unique([1,1,2]))
print(a)

результат:

[(2, 1, 1), (1, 2, 1), (1, 1, 2)]

РЕДАКТИРОВАТЬ (как это работает):

Я переписал вышеупомянутую программу, чтобы она была длиннее, но более читабельной.

Мне обычно трудно объяснить, как что-то работает, но позвольте мне попробовать. Чтобы понять, как это работает, вы должны понимать похожую, но более простую программу, которая выдает все перестановки с повторениями.

def permutations_with_replacement(elements,n):
    return permutations_helper(elements,[0]*n,n-1)#this is generator

def permutations_helper(elements,result_list,d):
    if d<0:
        yield tuple(result_list)
    else:
        for i in elements:
            result_list[d]=i
            all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
            for g in all_permutations:
                yield g

Эта программа, очевидно, намного проще: d обозначает глубину в permutations_helper и имеет две функции. Одна функция является условием остановки нашего рекурсивного алгоритма, а другая - для списка результатов, который передается.

Вместо того, чтобы возвращать каждый результат, мы получаем его. Если бы не было функции / оператора yield, мы бы поместили результат в некоторую очередь в точке условия остановки. Но таким образом, как только условие остановки выполнено, результат распространяется по всем стекам до вызывающей стороны. Это цель
for g in perm_unique_helper(listunique,result_list,d-1): yield g поэтому каждый результат распространяется до вызывающей стороны.

Вернуться к исходной программе: у нас есть список уникальных элементов. Прежде чем мы сможем использовать каждый элемент, мы должны проверить, сколько из них все еще доступно для добавления в result_list. Работа с этой программой очень похожа на permutations_with_replacement. Разница в том, что каждый элемент не может повторяться больше раз, чем в perm_unique_helper.

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

Answer 3

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

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

Answer 4

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

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.

Answer 5

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

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

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

Answer 6

Это моё решение с 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]]

Answer 7

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

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

---

Подробности

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

Answer 8

Похоже, вы ищете itertools.combination () docs.python.org

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

Answer 9

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

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

Answer 10

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

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

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

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