1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – JBL
    May 18, 2010 at 3:27
  • $\begingroup$ You can do this in GAP, for example: gap> Derangements([1,1,2,3]); $\endgroup$ May 18, 2010 at 3:54
  • $\begingroup$ 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. $\endgroup$ May 18, 2010 at 4:41
  • $\begingroup$ Okay. P.S. If anyone wants to see the GAP code type Print(Derangements,"\n"); and Print(DerangementsK,"\n"); $\endgroup$ May 18, 2010 at 5:34
  • $\begingroup$ 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. $\endgroup$
    – Ross Tang
    May 19, 2010 at 3:27

2 Answers 2

1
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ The link is dead! $\endgroup$
    – ajay
    May 26, 2015 at 10:09
0
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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