Python shuffle such that position will never repeat

I'd like to do a random shuffle of a list but with one condition: an element can never be in the same original position after the shuffle.

Is there a one line way to do such in python for a list?

Example:

list_ex = [1,2,3]

each of the following shuffled lists should have the same probability of being sampled after the shuffle:

list_ex_shuffled = [2,3,1]
list_ex_shuffled = [3,1,2]

but the permutations [1,2,3], [1,3,2], [2,1,3] and [3,2,1] are not allowed since all of them repeat one of the elements positions.

NOTE: Each element in the list_ex is a unique id. No repetition of the same element is allowed.

python random shuffle

Edit Report

1 Answer

Here's another algorithm. Take cards at random. If your ith card is card i, put it back and try again. Only problem, what if when you get to the last card it's the one you don't want. Swap it with one of the others.

I think this is fair (uniformally random).

import random

def permutation_without_fixed_points(n):
    if n == 1:
        raise ArgumentError, "n must be greater than 1"

    result = []
    remaining = range(n)

    i = 0
    while remaining:
        if remaining == [n-1]:
            break

        x = i
        while x == i:
            j = random.randrange(len(remaining))
            x = remaining[j]

        remaining.pop(j)
        result.append(x)

        i += 1

    if remaining == [n-1]:
        j = random.randrange(n-1)
        result.append(result[j])
        result[j] = n

    return result

answered 2013-03-20T00:43:17.030

Python shuffle such that position will never repeat

1 Answer

Your Answer