How to compute derangement (permutation) of a list with repeating elements

Question

I have a list with repeating elements, i.e. orig = [1,1,1,2,2,3].
I want to create a derangement b = f(orig) such that for every location value in b is different from value in orig:

b[i] != orig[i], for all i

I know a solution when all element in orig are unique, but this is a harder case.

Developing a solution in python, but any language will do.

you can just iterate through the permutations until you find one that is actually a derangement. It will not be very efficient but will do — Ma0, Oct 17 '18 at 11:48
This seems out of scope, since you offer no solution attempt. But in principle it should work like: generate any random permutation. Identify two different indices, where the permuted value is against your expectations still identical to orignal. Swap these positions. — guidot, Oct 17 '18 at 11:54
@guidot Would such a heuristic generate such permutations with uniform probability? — John Coleman, Oct 17 '18 at 11:57
Yes, it would, if the initial permutation is random (but the original would also do) and you start at a random position and consider the list a cyclic for the reamaining swaps. There are also special cases, where a solution is impossible as in `[1, 1, 2]`, which should be considered. — guidot, Oct 17 '18 at 12:01
@guidot I have implementation that works on similar principle but was hoping for something more elegant/efficient or simply standardised. Thanks though. — Tautvydas, Oct 17 '18 at 12:29
Adapted one of the solutions I offered to this task. Pretty efficient I think :) — Roelant, Oct 17 '18 at 14:41

Roelant · Answer 1 · 2018-10-17T14:47:06.097

The not so-efficient solution is clearly

import itertools
set([s for s in itertools.permutations(orig) if not any([a == b for a, b in zip(s, orig)])])

A second method and first improvement is using this perm_unique:

 [s for s in perm_unique(orig) if not any([a == b for a, b in zip(s, orig)])]

A third method is to use this super quick unique_permutations algorithm.

 import copy
 [copy.copy(s) for s in unique_permutations(orig) if not any([a == b for a, b in zip(s, orig)])]

In my notebook with %%timeit the initial method takes 841 µs, and we improve to 266 µs and then to 137 µs.

Edit

Couldn't stop considering, made a small edit of the second method. Didn't have the time to dive into the last method. For explanation, first see the original post (link above). Then I only added the check and el != elements[depth] which forces the condition of the derangement. With this we arrive at a running time of 50 µs.

from collections import Counter

def derangement_unique(elements):
    list_unique = Counter(elements)
    length_list = len(elements)  # will become depth in the next function
    placeholder = [0]*length_list  # will contain the result
    return derangement_unique_helper(elements, list_unique, placeholder, length_list-1)

def derangement_unique_helper(elements, list_unique, result_list, depth):
    if depth < 0:   # arrived at a solution
        yield tuple(result_list)
    else:
        # consider all elements and how many times they should still occur 
        for el, count in list_unique.items():
            # ... still required and not breaking the derangement requirement
            if count > 0 and el != elements[depth]:   
                result_list[depth] = el  # assignment element
                list_unique[el] -= 1   # substract number needed
                # loop for all possible continuations 
                for g in derangement_unique_helper(elements, list_unique, result_list, depth-1):
                    yield g
                list_unique[el] += 1


list(derangement_unique(orig))

score 0 · Answer 2 · answered Oct 17 '18 at 15:06

If your list contains significant part of duplicates, it might be hard to find derangement quickly.

In this case you can try graph approach.

Treat initial list to make a graph where every item is connected with non-equal elements (easy for sorted list).

Then build perfect matching (if number of element is even) or near-perfect matching (for odd count, here you'll need find some suitable pair and join single node to it).

Edges of matching indicate swaps to make derangement.

Python library networkx should contain needed methods.

How to compute derangement (permutation) of a list with repeating elements

2 Answers2

Linked