Generating all derangements of a multiset?

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!

• Well, there was an earlier question that generalized this, but I don't know that the comments there will be very helpful to you: mathoverflow.net/questions/23878/… If you were only interested in enumeration then mathoverflow.net/questions/20867/derangements-with-repetition would probably be helpful.
– JBL
May 18, 2010 at 3:27
• You can do this in GAP, for example: gap> Derangements([1,1,2,3]); May 18, 2010 at 3:54
• I can enumerate them - I found a simple method in Percy Macmahon's "Combinatory Analysis" (1915) - and I know that GAP has a procedure for listing them. I could also reverse-engineer the GAP code to determine the algorithm. But what I'm looking for is a book or paper which actually describes the procedure. May 18, 2010 at 4:41
• Okay. P.S. If anyone wants to see the GAP code type Print(Derangements,"\n"); and Print(DerangementsK,"\n"); May 18, 2010 at 5:34
• May I know if: Derangements([1,1,2,3]) = [[3, 2, 1, 1], [2, 3, 1, 1], [3, 2, 1, 1], [2, 3, 1, 1]] ? If so, I have written a short program to do this, and a bit description as well. I can post it here, if it is correct. If not, please tell me the expected output. Thank you. May 19, 2010 at 3:27

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()
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
sol = sol1
return list(sol)

– ajay
May 26, 2015 at 10:09

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