Generating all derangements of a multiset?

Question

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!

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)

Answer 2

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