Generate a random derangement of a list

by

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.

More Related Contents:

  1. Python, How to remove gaps between text and variable?
  2. How to generate all permutations of a list?
  3. Shuffling a list of objects
  4. Random string generation with upper case letters and digits
  5. Generate random numbers with a given (numerical) distribution
  6. Generate ‘n’ unique random numbers within a range [duplicate]
  7. Why does random.shuffle return None?
  8. Generating permutations with repetitions
  9. How to get a random number between a float range?
  10. What is the most pythonic way to pop a random element from a list?
  11. How do you pick “x” number of unique numbers from a list in Python?
  12. Generate a random letter in Python
  13. Generating random dates within a given range in pandas
  14. Differences between numpy.random and random.random in Python
  15. Random row selection in Pandas dataframe
  16. Sampling uniformly distributed random points inside a spherical volume
  17. How to specify upper and lower limits when using numpy.random.normal
  18. Fast arbitrary distribution random sampling (inverse transform sampling)
  19. How do I pick 2 random items from a Python set? [duplicate]
  20. Better way to shuffle two numpy arrays in unison
  21. How can I get a random key-value pair from a dictionary?
  22. How to generate a random UUID which is reproducible (with a seed) in Python
  23. Getting random row through SQLAlchemy
  24. Vectorizing `numpy.random.choice` for given 2D array of probabilities along an axis
  25. Comparing Matlab and Numpy code that uses random number generation
  26. Working with floating point NumPy arrays for comparison and related operations
  27. Maximal Length of List to Shuffle with Python random.shuffle?
  28. Best way to choose a random file from a directory
  29. Generate random number in range excluding some numbers
  30. Random numbers generation in PySpark

Leave a Comment