16

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.

Ravindra S
  • 6,302
  • 12
  • 70
  • 108
Dnaiel
  • 7,622
  • 23
  • 67
  • 126
  • 2
    What would you expect when your list contains multiple items that are equal to each other. For example, what do you want to happen when the list is `[2, 2, 2]`? – crayzeewulf Mar 19 '13 at 22:56
  • A combination of using a [deque](http://docs.python.org/2/library/collections.html#collections.deque) and its `rotate` method could produce the expected result. But, in some cases as in the above comment you have no clearly defined the expected result. – sean Mar 19 '13 at 22:59
  • 1
    @crayzeewulf good point! the structure of my data will never encounter such case, thanks! – Dnaiel Mar 19 '13 at 23:45
  • @sean, would you mind giving me more details, sounds like a good approach to try, thanks! – Dnaiel Mar 19 '13 at 23:52

6 Answers6

9

Randomize in a loop and keep rejecting the results until your condition is satisfied:

import random

def shuffle_list(some_list):
    randomized_list = some_list[:]
    while True:
        random.shuffle(randomized_list)
        for a, b in zip(some_list, randomized_list):
            if a == b:
                break
        else:
            return randomized_list
tdelaney
  • 73,364
  • 6
  • 83
  • 116
  • thanks, this is what i thought at the beginning, not sure how efficient in terms of time would be though... – Dnaiel Mar 19 '13 at 23:50
  • 1
    The expected number of shuffles necessary is *e*, which is less than 3 http://stackoverflow.com/a/15513026/284795 – Colonel Panic Mar 20 '13 at 00:32
  • @Dnaiel - efficiency would only be a problem for large lists or many iterations. It's easy to reduce randomness when getting clever with optimization. This solution doesn't make me have to think too hard. – tdelaney Mar 20 '13 at 03:55
8

I'd describe such shuffles as 'permutations with no fixed points'. They're also known as derangements.

The probability that a random permutation is a derangement is approximately 1/e (fun to prove). This is true however long the list. Thus an obvious algorithm to give a random derangement is to shuffle the cards normally, and keep shuffling until you have a derangement. The expected number of necessary shuffles is about 3, and it's rare you'll have to shuffle more than ten times.

(1-1/e)**11 < 1%

Suppose there are n people at a party, each of whom brought an umbrella. At the end of the party, each person takes an umbrella at random from the basket. What is the probability that no-one holds their own umbrella?

Colonel Panic
  • 132,665
  • 89
  • 401
  • 465
4

You could generate all possible valid shufflings:

>>> list_ex = [1,2,3]
>>> import itertools

>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                        itertools.permutations(list_ex, len(list_ex))))
[(2, 3, 1), (3, 1, 2)]

For some other sequence:

>>> list_ex = [7,8,9,0]
>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                        itertools.permutations(list_ex, len(list_ex))))
[(8, 7, 0, 9), (8, 9, 0, 7), (8, 0, 7, 9), (9, 7, 0, 8), (9, 0, 7, 8), (9, 0, 8, 7), (0, 7, 8, 9), (0, 9, 7, 8), (0, 9, 8, 7)]

You could also make this a bit more efficient by short-circuiting the iterator if you just want one result:

>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                       itertools.permutations(list_ex, len(list_ex)))
>>> next(i)
(2, 3, 1)

But, it would not be a random choice. You'd have to generate all of them and choose one for it to be an actual random result:

>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                       itertools.permutations(list_ex, len(list_ex)))
>>> import random
>>> random.choice(list(i))
(2, 3, 1)
jterrace
  • 64,866
  • 22
  • 157
  • 202
1

Here is another take on this. You can pick one solution or another depending on your needs. This is not a one liner but shuffles the indices of elements instead of the elements themselves. Thus, the original list may have duplicate values or values of types that cannot be compared or may be expensive to compare. 

#! /usr/bin/env python
import random

def shuffled_values(data):
    list_length = len(data)
    candidate = range(list_length)
    while True:
        random.shuffle(candidate)
        if not any(i==j for i,j in zip(candidate, range(list_length))):
            yield [data[i] for i in candidate]

list_ex = [1, 2, 3]
list_gen = shuffled_values(list_ex)
for i in range(0, 10):
    print list_gen.next()

This gives: 

[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[2, 3, 1]
[3, 1, 2]
[2, 3, 1]

If list_ex is [2, 2, 2], this method will keep yielding [2, 2, 2] over and over. The other solutions will give you empty lists. I am not sure what you want in this case.

crayzeewulf
  • 5,840
  • 1
  • 27
  • 30
1

Use Knuth-Durstenfeld to shuffle the list. As long as it is found to be in the original position during the shuffling process, a new shuffling process is started from the beginning until it returns to a qualified arrangement. The time complexity of this algorithm is the smallest constant term:

def _random_derangement(x: list, randint: Callable[[int, int], int]) -> None:
    '''
        Random derangement list x in place, and return None.
        An element can never be in the same original position after the shuffle. provides uniform distribution over permutations.
        The formal parameter randint requires a callable object such as rand_int(b, a) that generates a random integer within the specified closed interval.
    '''

    from collections import namedtuple

    sequence_type = namedtuple('sequence_type', ('sequence_number', 'elem'))

    x_length = len(x)
    if x_length > 1:
        for i in range(x_length):
            x[i] = sequence_type(sequence_number = i, elem = x[i])
    
        end_label = x_length - 1
        while True:
            for i in range(end_label, 0, -1):
                random_location = randint(i, 0)
                if x[random_location].sequence_number != i:
                    x[i], x[random_location] = x[random_location], x[i]
                else:
                    break
            else:
                if x[0].sequence_number != 0: break
    
        for i in range(x_length):
            x[i] = x[i].elem

complete_shuffle

sosei
  • 21
  • 2
0

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
Colonel Panic
  • 132,665
  • 89
  • 401
  • 465