Generate a Random Derangement of a List

Generate a random derangement of a list

After some research I was able to implement the "early refusal" algorithm as described e.g. in this paper [1]. It goes like this:

import random

def random_derangement(n):
    while True:
        v = [i for i in range(n)]
        for j in range(n - 1, -1, -1):
            p = random.randint(0, j)
            if v[p] == j:
                break
            else:
                v[j], v[p] = v[p], v[j]
        else:
            if v[0] != 0:
                return tuple(v)

The idea is: we keep shuffling the array, once we find that the permutation we're working on is not valid (v[i]==i), we break and start from scratch.

A quick test shows that this algorithm generates all derangements uniformly:

N = 4

# enumerate all derangements for testing
import itertools
counter = {}
for p in itertools.permutations(range(N)):
    if all(p[i] != i for i in p):
        counter[p] = 0

# make M probes for each derangement
M = 5000
for _ in range(M*len(counter)):
    # generate a random derangement
    p = random_derangement(N)
    # is it really?
    assert p in counter
    # ok, record it
    counter[p] += 1

# the distribution looks uniform
for p, c in sorted(counter.items()):
    print p, c

Results:

(1, 0, 3, 2) 4934
(1, 2, 3, 0) 4952
(1, 3, 0, 2) 4980
(2, 0, 3, 1) 5054
(2, 3, 0, 1) 5032
(2, 3, 1, 0) 5053
(3, 0, 1, 2) 4951
(3, 2, 0, 1) 5048
(3, 2, 1, 0) 4996

I choose this algorithm for simplicity, this presentation [2] briefly outlines other ideas.

References:

• [1] An analysis of a simple algorithm for random derangements. Merlini, Sprugnoli, Verri. WSPC Proceedings, 2007.
• [2] Generating random derangements. Martínez, Panholzer, Prodinger.

How do I generate a random derangement of a list/array in java?

What about using a SortedMap where your keys are going to be random, like this:

public static int[] derangement(int n){
    Random rand = new Random();
    int[] result = new int[n];
    SortedMap<Double, Integer> map = new TreeMap<>();
    for (int i = 0; i < n; i++) {
        map.put(rand.nextDouble(), i);
    }
    int i = 0;
    for (Double key: map.keySet()) {
        result[i] = map.get(key);
        i++;
    }
    return result;
}

This way, as the random keys in your map become ordered, you are shuffling the list.

Guaranteed shuffling of a list

To generate a derangement, you can use the Fisher-Yates shuffling algorithm and just exclude the current index from consideration when selecting an index to swap with (i.e., do not allow swapping an element with itself).

Python: How to random shuffle a list where each variable will end up in a new place

Something like this should do what you want:

import random
import copy

def super_shuffle(lst):
    new_lst = copy.copy(lst)
    random.shuffle(new_lst)
    for old, new in zip(lst, new_lst):
        if old == new:
            return super_shuffle(lst)

    return new_lst

Example:

In [16]: super_shuffle(['a', 'b', 'c'])
Out[16]: ['b', 'c', 'a']

Fast randomly-paired permutation

The pairing of swaps would imply that N is always an even number. If that is the case, then you can take a sample of half the indexes and pair them with a shuffled list of the remaining indexes:

import random
def randomPairs(N):
    result = [None] * N
    A  = random.sample(range(N),N//2)
    B  = random.sample(list(set(range(N))-set(A)),N//2)
    for a,b in zip(A,B):
        result[a] = b
        result[b] = a
    return result

for _ in range(10):
    print(randomPairs(6))

[4, 3, 5, 1, 0, 2]
[5, 4, 3, 2, 1, 0]
[5, 3, 4, 1, 2, 0]
[2, 3, 0, 1, 5, 4]
[3, 2, 1, 0, 5, 4]
[2, 3, 0, 1, 5, 4]
[4, 2, 1, 5, 0, 3]
[3, 4, 5, 0, 1, 2]
[2, 3, 0, 1, 5, 4]
[1, 0, 3, 2, 5, 4]

Performance

# 1000 shuffles of 1500 elements in pairs
def test1():
    for _ in range(1000):
        randomPairs(1500)
        
from timeit import timeit
count = 1

t = timeit(test1,number=count)
print(t) # 1.12 seconds

[EDIT] a slightly faster solution would be to shuffle all the indexes and pair every other position with the next one in the shuffled list:

import random
def randomPairs(N):
    result = [None] * N
    A  = random.sample(range(N),N)
    for a,b in zip(A[::2],A[1::2]):
        result[a] = b
        result[b] = a
    return result

---

Related Topics