Как сгенерировать все перестановки мультимножества?
Мультимножество - это множество, в котором все элементы не могут быть уникальными. Как перечислить все возможные перестановки среди элементов множества?
6 ответов
Генерация всех возможных перестановок, а затем отбрасывание повторных крайне неэффективна. Существуют различные алгоритмы для непосредственного генерирования перестановок мультимножества в лексикографическом порядке или в другом порядке. Алгоритм Такаоки - хороший пример, но, вероятно, алгоритм Аарона Уильямса лучше
http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf
кроме того, он был реализован в пакете R '' multicool ''.
Кстати, если вы просто хотите получить общее количество различных перестановок, ответом является множительный коэффициент: например, если у вас есть, скажем, элементы n_a 'a', элементы n_b 'b', элементы n_c 'c', общее количество различная перестановка есть (n_a+n_b+n_c)!/(n_a!n_b!n_c!)
sympy обеспечивает multiset_permutations.
из документа:
>>> from sympy.utilities.iterables import multiset_permutations
>>> from sympy import factorial
>>> [''.join(i) for i in multiset_permutations('aab')]
['aab', 'aba', 'baa']
>>> factorial(len('banana'))
720
>>> len(list(multiset_permutations('banana')))
60
Это мой перевод алгоритма перестановок мультимножеств Takaoka на Python (доступен здесь и на repl.it):
def msp(items):
'''Yield the permutations of `items` where items is either a list
of integers representing the actual items or a list of hashable items.
The output are the unique permutations of the items given as a list
of integers 0, ..., n-1 that represent the n unique elements in
`items`.
Examples
========
>>> for i in msp('xoxox'):
... print(i)
[1, 1, 1, 0, 0]
[0, 1, 1, 1, 0]
[1, 0, 1, 1, 0]
[1, 1, 0, 1, 0]
[0, 1, 1, 0, 1]
[1, 0, 1, 0, 1]
[0, 1, 0, 1, 1]
[0, 0, 1, 1, 1]
[1, 0, 0, 1, 1]
[1, 1, 0, 0, 1]
Reference: "An O(1) Time Algorithm for Generating Multiset Permutations", Tadao Takaoka
https://pdfs.semanticscholar.org/83b2/6f222e8648a7a0599309a40af21837a0264b.pdf
'''
def visit(head):
(rv, j) = ([], head)
for i in range(N):
(dat, j) = E[j]
rv.append(dat)
return rv
u = list(set(items))
E = list(reversed(sorted([u.index(i) for i in items])))
N = len(E)
# put E into linked-list format
(val, nxt) = (0, 1)
for i in range(N):
E[i] = [E[i], i + 1]
E[-1][nxt] = None
head = 0
afteri = N - 1
i = afteri - 1
yield visit(head)
while E[afteri][nxt] is not None or E[afteri][val] < E[head][val]:
j = E[afteri][nxt] # added to algorithm for clarity
if j is not None and E[i][val] >= E[j][val]:
beforek = afteri
else:
beforek = i
k = E[beforek][nxt]
E[beforek][nxt] = E[k][nxt]
E[k][nxt] = head
if E[k][val] < E[head][val]:
i = k
afteri = E[i][nxt]
head = k
yield visit(head)
Существует O(1) (для каждой перестановки) алгоритмы для генерации перестановок из множества множеств, например, из Takaoka (с реализацией)
Оптимизация ответа смихра user1089161 я разархивировалnxts сделать посещение более эффективным с помощьюaccumulate()(map()быстрее, чем понимание списка, и казалось поверхностным и педантичным вкладывать его во второй с постоянным индексом)
from itertools import accumulate
def msp(items):
def visit(head):
'''(rv, j) = ([], head)
for i in range(N):
(dat, j) = E[j]
rv.append(dat)
return(rv)'''
#print(reduce(lambda e,dontCare: (e[0]+[E[e[1]]],nxts[e[1]]),range(N),([],head))[0])
#print(list(map(E.__getitem__,accumulate(range(N-1),lambda e,N: nxts[e],initial=head))))
return(list(map(E.__getitem__,accumulate(range(N-1),lambda e,N: nxts[e],initial=head))))
u=list(set(items))
E=list(sorted(map(u.index,items)))
N=len(E)
nxts=list(range(1,N))+[None]
head=0
i,ai,aai=N-3,N-2,N-1
yield(visit(head))
while aai!=None or E[ai]>E[head]:
beforek=(i if aai==None or E[i]>E[aai] else ai)
k=nxts[beforek]
if E[k]>E[head]:
i=k
nxts[beforek],nxts[k],head = nxts[k],head,k
ai=nxts[i]
aai=nxts[ai]
yield(visit(head))
Вот результаты теста (у второго есть(13!/2!/3!/3!/4!)/10! = 143/144раз больше перестановок, но занимает больше времени из-за большего количества мультимножеств, я полагаю), мой кажется на 9% и 7% быстрее соответственно:
cProfile.run("list(msp(list(range(10))))")
cProfile.run("list(msp([0,1,1,2,2,2,3,3,3,3,4,4,4]))")
original:
43545617 function calls in 28.452 seconds
54054020 function calls in 32.469 seconds
modification:
39916806 function calls in 26.067 seconds
50450406 function calls in 30.384 seconds
У меня недостаточно репутации, чтобы комментировать ответы, но дляitemsвходной список, ответ user1405321 имеет временную сложность произведения факториалов количества экземпляров каждого значения элемента в разы больше, или
reduce(int.__mul__,map(lambda n: reduce(int.__mul__,range(1,n+1)),map(items.count,set(items))))
Это может быстро увеличиваться при вычислении больших мультимножеств с большим количеством вхождений. Например, для моего второго примера на одну перестановку потребуется в 1728 раз больше времени, чем для первого.
Вы можете уменьшить свою проблему, чтобы перечислить все перестановки списка. Алгоритм генерации типичных перестановок берет список и не проверяет, равны ли элементы. Таким образом, вам нужно только создать список из вашего мультимножества и передать его в свой алгоритм генерации перестановок.
Например, у вас есть мультисеть {1,2,2}.
Вы превращаете его в список [1,2,2].
И сгенерируйте все перестановки, например в python:
import itertools as it
for i in it.permutations([1,2,2]):
print i
И вы получите выход
(1, 2, 2)
(1, 2, 2)
(2, 1, 2)
(2, 2, 1)
(2, 1, 2)
(2, 2, 1)
Проблема в том, что вы получаете некоторые перестановки неоднократно. Простым решением будет просто отфильтровать их:
import itertools as it
permset=set([i for i in it.permutations([1,2,2])])
for x in permset:
print x
Выход:
(1, 2, 2)
(2, 2, 1)
(2, 1, 2)