CODEWITHSUNDEEP
pythonmathcombinationspermutation
Tautvydas
Tautvydas

Reputation: 2067

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

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.

Upvotes: 2

Views: 1177

Answers (2)

MBo
MBo

Reputation: 80187

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.

Upvotes: 0

Roelant
Roelant

Reputation: 5119

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))

Upvotes: 2

Related Questions