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.
Any ideas? thanks!
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
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)
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?
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.
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
