我想对列表进行随机洗牌，但有一个条件：洗牌后元素永远不能处于相同的原始位置。
有没有一种方法可以在 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] 是不允许的，因为它们都重复元素位置之一。
注意：list_ex 中的每个元素都是唯一的 id。不允许重复相同的元素。
有任何想法吗？谢谢！
在循环中随机化并不断拒绝结果，直到满足您的条件：
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
我将这种洗牌描述为“没有固定点的排列”。它们也被称为精神错乱。
随机排列是紊乱的概率大约是 1/e（证明起来很有趣）。不管清单有多长，这都是真的。因此，一个明显的随机混乱算法是正常洗牌，并继续洗牌，直到你有一个混乱。预期的必要洗牌次数约为 3，而且很少需要洗牌超过 10 次。
(1-1/e)**11 < 1%
假设聚会上有 n 个人，每个人都带了一把雨伞。聚会结束时，每个人从篮子里随机拿一把雨伞。没有人自己撑伞的概率是多少？
您可以生成所有可能的有效改组：
>>> 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)
这是对此的另一种看法。您可以根据需要选择一种或另一种解决方案。这不是一个单一的衬里，而是洗牌元素的索引而不是元素本身。因此，原始列表可能具有无法比较或比较昂贵的重复值或类型值。
#! /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()
这给出了：
[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]
如果list_ex是[2, 2, 2]，此方法将[2, 2, 2]一遍又一遍地让步。其他解决方案将为您提供空列表。我不确定在这种情况下你想要什么。
使用 Knuth-Durstenfeld 对列表进行洗牌。只要在洗牌过程中发现它在原来的位置，就从头开始一个新的洗牌过程，直到它回到一个合格的排列。该算法的时间复杂度是最小的常数项：
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
这是另一种算法。随机取卡。如果你的第i张卡是第i张卡，把它放回去再试一次。唯一的问题是，如果当您到达最后一张卡时，它是您不想要的那张。与其他之一交换它。
我认为这是公平的（均匀随机）。
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