Перестановки, которые не повторяются python

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

Например, список ["вверх", "вверх"] должен генерировать только список ["вверх", "вверх"], а не дважды.

Другой пример [ "вверх", "вверх", "правый"] возвращает только:

["up", "up", "right"] 
["up", "right", "up"] 
["right", "up", "up"]

, а не следующее:

["up", "up", "right"] 
["up", "right", "up"] 
["right", "up", "up"] 
["up", "up", "right"] 
["up", "right", "up"] 
["right", "up", "up"]

Например, этот сценарий не дает нужный список.

>>> import itertools 
>>> a = list(itertools.permutations(["up","up","down"])) 
>>> print a 
[('up', 'up', 'down'), ('up', 'down', 'up'), ('up', 'up', 'down'), ('up', 'down', 'up'), ('down', 'up', 'up'), ('down', 'up', 'up')]

Примечание:, как я могу сделать это быстрее с большими списками размером 20 или больше?

источник

2013-11-26 Monte Carlo

Нет. Мне просто нужно знать, сколько различных перестановок для 20 взлетов и 20 спадов. Каков наилучший способ сделать это? Python перехватил мяч вместо 42: 34.20. Должен быть лучший способ сделать это. –

Ах. Мы называем это [проблема XY] (http://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). По-видимому, ваш реальный вопрос: «Сколько четких кортежей существует с 20 взлетами и 20 падениями?» - это одна простая формула, не требующая Python, - но вместо того, чтобы спросить о вашей реальной проблеме, вы спросили: «Как мне создать длинный список перестановок быстрее?» – DSM

@DSM Что такое формула? Как вы решили 15, 15 для разных кортежей? –

Вы можете просто сделать

print list(set(a))

DEMO:

>>> import itertools 
>>> a = list(itertools.permutations(["up","up","down"])) 
>>> a 
[('up', 'up', 'down'), ('up', 'down', 'up'), ('up', 'up', 'down'), ('up', 'down', 'up'), ('down', 'up', 'up'), ('down', 'up', 'up')] 
>>> set(a) 
set([('up', 'up', 'down'), ('down', 'up', 'up'), ('up', 'down', 'up')]) 
>>> list(set(a)) 
[('up', 'up', 'down'), ('down', 'up', 'up'), ('up', 'down', 'up')] 
>>>

источник

2013-11-26 17:56:29 karthikr

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

>>> set(itertools.permutations(a)) 
set([('up', 'up', 'right'), ('right', 'up', 'up'), ('up', 'right', 'up')])

Это гарантирует, что вы не получаете дубликаты в вашем вывод.

Вы можете преобразовать набор в список с list(), конечно.

источник

2013-11-26 17:56:45

Есть ли способ сделать это быстрее? Мой список начинается с 30 единиц в длину, и мой код просто кажется зависающим, и мое использование процессора исчезает с графика. –

Это не вопрос Python, это математический вопрос. (В комментариях выяснилось, что OP не после самого списка, а просто для подсчета.)

Если у вас есть 30 слотов для заполнения 15 "вверх" и 15 "вниз", тогда вам нужно выбрать 15 различных мест из 30 возможных, чтобы поместить «вверх», а затем остальные вынуждены «опускаться».

Выбор 15 различных чисел из 30 30 выбрать 15 или 30 /! ((15) * ((30-15))!):

>>> from math import factorial 
>>> factorial(30)/factorial(15)/factorial(30-15) 
155117520L

Мы можем проверить это выражение вручную меньший список:

>>> from itertools import permutations 
>>> len(set(permutations(["up"]*7+["down"]*3))) 
120 
>>> factorial(10)/factorial(7)/factorial(10-7) 
120

источник

2013-11-26 19:48:33 DSM

Перестановки, которые не повторяются python

ответ

Смежные вопросы