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)
result:
[(2, 1, 1), (1, 2, 1), (1, 1, 2)]
EDIT (как это работает):
Я переписал верхнюю программу более длинной, но более читаемой
Обычно мне сложно объяснить, как что-то работает, но позвольте мне попробовать. Чтобы понять, как это работает, вам нужно понять схожую, но более простую программу, которая даст все перестановки с повторением.
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.
Как насчет
np.unique(itertools.permutations([1, 1, 1]))
Проблема заключается в том, что теперь перестановки представляют собой строки массива Numpy, тем самым используя больше памяти, но вы можете циклически их перемещать по-прежнему
perms = np.unique(itertools.permutations([1, 1, 1]))
for p in perms:
print p
В этом вопросе, когда я что-то искал сам!
Вот что я сделал:
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)])
В принципе, создайте набор и продолжайте добавлять к нему. Лучше, чем создавать списки и т. Д., Которые занимают слишком много памяти. Надеюсь, это поможет следующему человеку, смотрящему :-) Комментируйте набор «обновление» в функции, чтобы увидеть разницу.
Поскольку иногда новые вопросы отмечены как дубликаты, и их авторы ссылаются на этот вопрос, может быть важно упомянуть, что для этой цели у 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]]
Наступил другой день, когда я работал над собственной проблемой. Мне нравится подход Луки Ране, но я думал, что использование класса 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.combinations () docs.python.org
list(itertools.combinations([1, 1, 1],3))
[(1, 1, 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]]
more-itertools
. Ты согласен с этим?
– jferard
10 May 2018 в 10:39
Грубо так же быстро, как и ответ Луки Ране, но короче & amp; более простой, IMHO.
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
of (1,2,3,1), чтобы увидеть, как он работает:
unique_elements
- 1,2,3 first_element
начинается с 1. remaining_elements
- [2,3,1] (т. е. 1,2,3,1 минус первый 1). Мы перебираем (рекурсивно) через перестановки остальных элементов: (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. Я придумал очень подходящую реализацию, используя itertools.product в этом случае (это реализация, где вы хотите все комбинации
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.product () итерации от k = 0 до k = X, последующая фильтрация с подсчетом гарантирует, что в список будут внесены только перестановки с правильным количеством единиц. Вы можете легко увидеть, что это работает, когда вы вычислить n над k и сравнить его с len (unique_perm_list)
Вы можете попробовать использовать set:
>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 1)]
Вызов для установки удаленных дубликатов
list(itertools.permutations({1,1,2,2}))
в Python 3+ или Python 2.7 из-за существования множества литералов. Хотя, если он не использует буквенные значения, он все равно будет использовать set()
. И @ralu: снова посмотрите на вопрос, потом фильтрация будет дорогостоящей.
– JAB
8 June 2011 в 21:08
list(itertools.permutations([1, 1, 0, 'x']))
, но с дубликатами, где они меняются местами.
– xyz-123
8 June 2011 в 21:14
itertools.product((0, 1, 'x'), repeat=X)
, но мне нужно обрабатывать значения с небольшим количеством «х» (отсортировано не подходит, потому что оно генерирует список и использование слишком большого объема памяти).
– xyz-123
8 June 2011 в 21:25
Здесь рекурсивное решение проблемы.
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))
Наивный подход может заключаться в том, чтобы взять набор перестановок:
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
на порядок быстрее.
Подробности
Из исходного кода алгоритм рекурсии (как показано в принятом ответе) используется для вычисления различных перестановок, тем самым устраняя расточительные вычисления. Подробнее см. Исходный код .
Это полагается на деталь реализации, что любая перестановка отсортированного итерабельного в отсортированном порядке, если они не являются дубликатами предшествующих перестановок.
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')
itertools.Counter
, верно? – Eric Duminil 13 February 2018 в 23:46