permutations with unique values

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 слишком велики.

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

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 .

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

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

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

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

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.