Generate a random derangement of a list

Question

How can I randomly shuffle a list so that none of the elements remains in its original position?

In other words, given a list A with distinct elements, I'd like to generate a permutation B of it so that

• this permutation is random
• and for each n, a[n] != b[n]

e.g.

a = [1,2,3,4]
b = [4,1,2,3] # good
b = [4,2,1,3] # good

a = [1,2,3,4]
x = [2,4,3,1] # bad

I don't know the proper term for such a permutation (is it "total"?) thus having a hard time googling. The correct term appears to be "derangement".

Answer 1

After some research I was able to implement the "early refusal" algorithm as described e.g. in this paper. 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 briefly outlines other ideas.

Answer 2

Such permutations are called derangements. In practice you can just try random permutations until hitting a derangement, their ratio approaches the inverse of 'e' as 'n' grows.

Answer 3

As a possible starting point, the Fisher-Yates shuffle goes like this.

def swap(xs, a, b):
    xs[a], xs[b] = xs[b], xs[a]

def permute(xs):
    for a in xrange(len(xs)):
        b = random.choice(xrange(a, len(xs)))
        swap(xs, a, b)

Perhaps this will do the trick?

def derange(xs):
    for a in xrange(len(xs) - 1):
        b = random.choice(xrange(a + 1, len(xs) - 1))
        swap(xs, a, b)
    swap(len(xs) - 1, random.choice(xrange(n - 1))

Here's the version described by Vatine:

def derange(xs):
    for a in xrange(1, len(xs)):
        b = random.choice(xrange(0, a))
        swap(xs, a, b)
    return xs

A quick statistical test:

from collections import Counter

def test(n):
    derangements = (tuple(derange(range(n))) for _ in xrange(10000))
    for k,v in Counter(derangements).iteritems():
        print('{}   {}').format(k, v)

test(4):

(1, 3, 0, 2)   1665
(2, 0, 3, 1)   1702
(3, 2, 0, 1)   1636
(1, 2, 3, 0)   1632
(3, 0, 1, 2)   1694
(2, 3, 1, 0)   1671

This does appear uniform over its range, and it has the nice property that each element has an equal chance to appear in each allowed slot.

But unfortunately it doesn't include all of the derangements. There are 9 derangements of size 4. (The formula and an example for n=4 are given on the Wikipedia article).