python shuffle这样的位置永远不会重复

Question

我想做一个列表的随机随机但有一个条件:一个元素在shuffle之后永远不会处于相同的原始位置.

有没有一种方法可以在python中为列表执行此操作？

例:

list_ex = [1,2,3]

以下每个混洗列表应该在shuffle之后具有相同的采样概率:

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

但是不允许排列[1,2,3],[1,3,2],[2,1,3]和[3,2,1],因为它们都重复了一个元素位置.

注意:list_ex中的每个元素都是唯一的id.不允许重复相同的元素.

有任何想法吗？谢谢!

Answer 1

在循环中随机化并继续拒绝结果,直到满足条件:

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

Answer 2

我将这种洗牌描述为“没有固定点的排列”。它们也被称为紊乱。

随机排列是混乱的概率大约是 1/e（证明很有趣）。无论列表有多长，这都是正确的。因此，给出随机混乱的一个明显算法是正常洗牌，并继续洗牌，直到出现混乱。预期的必要 shuffle 次数约为 3，而且很少需要 shuffle 超过 10 次。

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

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

Answer 3

您可以生成所有可能的有效shuffling:

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