Generate a random derangement of a list

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".

Solution 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.

Solution 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.

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

Solution 4:

This should work

import random

totalrandom = False
array = [1, 2, 3, 4]
it = 0
while totalrandom == False:
    it += 1
    shuffledArray = sorted(array, key=lambda k: random.random())
    total = 0
    for i in array:
        if array[i-1] != shuffledArray[i-1]: total += 1
    if total == 4:
        totalrandom = True

    if it > 10*len(array):
        print("'Total random' shuffle impossible")
        exit()
print(shuffledArray)

Note the variable it which exits the code if too many iterations are called. This accounts for arrays such as [1, 1, 1] or [3]

EDIT

Turns out that if you're using this with large arrays (bigger than 15 or so), it will be CPU intensive. Using a randomly generated 100 element array and upping it to len(array)**3, it takes my Samsung Galaxy S4 a long time to solve.

EDIT 2

After about 1200 seconds (20 minutes), the program ended saying 'Total Random shuffle impossible'. For large arrays, you need a very large number of permutations... Say len(array)**10 or something.

Code:

import random, time

totalrandom = False
array = []
it = 0

for i in range(1, 100):
    array.append(random.randint(1, 6))

start = time.time()

while totalrandom == False:
    it += 1
    shuffledArray = sorted(array, key=lambda k: random.random())
    total = 0
    for i in array:
        if array[i-1] != shuffledArray[i-1]: total += 1
    if total == 4:
        totalrandom = True

    if it > len(array)**3:
        end = time.time()
        print(end-start)
        print("'Total random' shuffle impossible")
        exit()

end = time.time()
print(end-start)
print(shuffledArray)