# 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 '10 at 3:27
You can do this in GAP, for example: gap> Derangements([1,1,2,3]); –  Douglas S. Stones May 18 '10 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. –  Alasdair McAndrew May 18 '10 at 4:41
Okay. P.S. If anyone wants to see the GAP code type Print(Derangements,"\n"); and Print(DerangementsK,"\n"); –  Douglas S. Stones May 18 '10 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. –  Ross Tang May 19 '10 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()