перестановки с уникальными значениями
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.