Python洗牌使得位置不重复

Question

我想对一个列表进行随机打乱，但有一个条件：打乱后，任何元素都不能回到它原来的位置。

在Python中，有没有一种一行代码就能做到这一点的方法？

举个例子：

list_ex = [1,2,3]

每个打乱后的列表都应该有相同的概率被选中：

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

但是像[1,2,3]、[1,3,2]、[2,1,3]和[3,2,1]这样的排列是不允许的，因为它们都有元素回到了原来的位置。

注意：列表中的每个元素都是唯一的ID，不允许有重复的元素。

Answer 1

你可以生成所有可能的有效洗牌结果：

>>> 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)]

对于其他一些序列：

>>> 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)]

如果你只想要一个结果，可以通过提前结束迭代器来让这个过程更高效：

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

不过，这样得到的结果并不是一个随机选择。你必须生成所有结果，然后从中选一个，这样才能算是真正的随机结果：

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

Answer 2

我会把这种洗牌称为“没有固定点的排列”。它们也被称为错位排列。

随机排列成错位排列的概率大约是1/e（这个证明起来很有趣）。这对于任何长度的列表都是成立的。因此，一个明显的算法来得到一个随机的错位排列就是正常地洗牌，然后继续洗牌，直到得到一个错位排列。预计需要洗牌的次数大约是3次，而且你很少需要洗牌超过10次。

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

---

假设有n个人在一个聚会上，每个人都带了一把伞。聚会结束时，每个人从篮子里随机拿一把伞。那么没有人拿到自己伞的概率是多少呢？

Answer 3

在一个循环中随机生成结果，并不断拒绝这些结果，直到满足你的条件为止：

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