2

1

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!

flag
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/… 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]); – Douglas S. Stones 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. – Alasdair McAndrew 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"); – Douglas S. Stones 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. – Ross Tang May 19 2010 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)
link|flag

Your Answer

Get an OpenID
or

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