I'm trying to find a reference to an algorithm for generating all the derangements of a multiset (this is not my area of expertise, by the way!), and so far I have found plenty on derangements of sets, but not much on multisets. Can anyone point me in the direction of a useful paper or text?
Thanks!
Please refer A procedure to list all derangements of a multiset for the explanation, and the following is the python code for all the derangements of a multiset vs:
def derangement(vs):
l = [None for x in vs]
sol = set()
sol.add(tuple(l))
for v in vs:
sol1 = set()
for s in sol:
for (i, v1) in enumerate(s):
if not v1 and v != vs[i]:
s1 = list(s)
s1[i] = v
sol1.add(tuple(s1))
sol = sol1
return list(sol)
The following routine (modified slightly from here) does not store up solutions and does not run out of memory as easily as the routine above:
def derangements(S):
"""Yield unique derangements of S which is comprised of hashable
elements.
Examples
========
>>> [''.join(i) for i in derangements('abbcc')]
['bccba', 'bccab', 'cacbb', 'ccabb']
The return value is a list of elements of S which is modified
internally in place, so a copy of the return value should be
made if collecting the results in a list (or strings should be
joined as shown above):
>>> [i for i in derangements([1,2,3,3])]
[[3, 3, 2, 1], [3, 3, 2, 1]]
>>> [i.copy() for i in derangements([1,2,3,3])]
[[3, 3, 1, 2], [3, 3, 2, 1]]
"""
from collections import Counter as multiset
from itertools import combinations as subsets
# S must contain hashable elements
s = set(S)
# at each position, these are what may be used
P = [sorted(s - set([k])) for k in S]
# these are the counts of each element
C = multiset(S)
# the index to what we are using at each position
I = [0]*len(P)
# the list of return values that will be modified in place
rv = [None]*len(P)
# we know the value that occurs most will be located in subsets
# of the other positions so find those positions...
mx = max(C.values())
for M in sorted(C):
if C[M] == mx:
break
ix = [i for i,c in enumerate(S) if c != M]
# remove M from its current locations...
for i in ix:
P[i].remove(M)
# and make them fixed points each time.
for fix in subsets(ix, mx):
p = P.copy()
for i in fix:
p[i] = [M]
while 1:
Ci = C.copy()
for k, pk in enumerate(p):
c = pk[I[k]]
if Ci[c] == 0:
# can't select this at position k
break
else:
Ci[c] -= 1
rv[k] = c
else:
yield(rv)
# increment last valid index
I[k] = (I[k] + 1)%len(p[k])
if I[k] == 0:
# set all to the right back to 0
I[k + 1:] = [0]*(len(I) - k - 1)
# carry to the left
while k and I[k] == 0:
k -= 1
I[k] = (I[k] + 1)%len(p[k])
if k == 0 and I[k] == 0:
break
