Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.