我想对一个列表进行随机洗牌,但有一个条件:在混洗之后,元素永远不会处于相同的原始位置。
在python for a list中,有没有一行的方法来实现这一点?
示例:
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]是不允许的,因为它们都重复元素位置中的一个。
注意:list_ex中的每个元素都是唯一的ID。不允许重复使用相同的元素。
6条答案
按热度按时间lskq00tm1#
在循环中进行随机化,并不断拒绝结果,直到满足您的条件:
enxuqcxy2#
我将这种洗牌描述为“没有固定点的排列”,它们也被称为derangements。
一个随机排列是错乱的概率约为1/e(证明起来很有趣)。无论列表有多长,这都是正确的。因此,给予随机错乱的一个明显算法是正常地洗牌,并且一直洗牌,直到你出现错乱。预期的必要洗牌次数约为3次,很少你需要洗牌超过10次。
假设有n个人参加聚会,每个人都带了一把伞。聚会结束时,每个人都从篮子里随机拿了一把伞。没有人带自己的伞的概率是多少?
vs91vp4v3#
您可以生成所有可能的有效洗牌:
对于其他序列:
如果只需要一个结果,还可以通过短路迭代器来提高效率:
但是,这并不是一个“随机”的选择,你必须生成所有的选项,然后从中选择一个,这样才是一个真正的随机结果:
1qczuiv04#
这是另一个解决方案。你可以根据自己的需要选择一个或另一个解决方案。这不是一个单行程序,而是打乱元素的索引,而不是元素本身。因此,原始列表可能有重复的值,或者无法比较的类型值,或者比较起来可能很昂贵。
这给出:
如果
list_ex
是[2, 2, 2]
,这个方法会不断地产生[2, 2, 2]
。其他的解决方案会给予你空的列表。我不确定在这种情况下你想要什么。lp0sw83n5#
使用Knuth-Durstenfeld对列表进行洗牌,在洗牌过程中只要发现它在原来的位置,就从头开始一个新的洗牌过程,直到它回到一个合格的排列,这个算法的时间复杂度是最小的常数项:
complete_shuffle
kcugc4gi6#
这是另一个算法,随机取牌,如果你的第i张牌是第i张,把它放回去再试一次,唯一的问题是,如果你拿到最后一张牌时,它是你不想要的,那就把它和其他牌交换一下。
我认为这是公平的(均匀随机)。