Вопрос-Ответ

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

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

Переведено автоматически
Ответ 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 .

Ответ 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]]
Ответ 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')
Ответ 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.

python