如何随机打乱列表，以便没有元素保留在其原始位置？
换句话说，给定一个具有不同元素的列表
ABna[n] != b[n]例如
a = [1,2,3,4]
b = [4,1,2,3] # good
b = [4,2,1,3] # good
a = [1,2,3,4]
x = [2,4,3,1] # bad
我不知道这种排列的正确术语（是“全部”吗？），因此很难用谷歌搜索。正确的术语似乎是“混乱”。
经过一些研究，我能够实现“早期拒绝”算法，例如在本文[1]中。事情是这样的：
import random
def random_derangement(n):
while True:
v = [i for i in range(n)]
for j in range(n - 1, -1, -1):
p = random.randint(0, j)
if v[p] == j:
break
else:
v[j], v[p] = v[p], v[j]
else:
if v[0] != 0:
return tuple(v)
我们的想法是：我们不断地对数组进行洗牌，一旦我们发现我们正在处理的排列无效（
v[i]==i快速测试表明该算法统一生成所有混乱：
N = 4
# enumerate all derangements for testing
import itertools
counter = {}
for p in itertools.permutations(range(N)):
if all(p[i] != i for i in p):
counter[p] = 0
# make M probes for each derangement
M = 5000
for _ in range(M*len(counter)):
# generate a random derangement
p = random_derangement(N)
# is it really?
assert p in counter
# ok, record it
counter[p] += 1
# the distribution looks uniform
for p, c in sorted(counter.items()):
print p, c
结果：
(1, 0, 3, 2) 4934
(1, 2, 3, 0) 4952
(1, 3, 0, 2) 4980
(2, 0, 3, 1) 5054
(2, 3, 0, 1) 5032
(2, 3, 1, 0) 5053
(3, 0, 1, 2) 4951
(3, 2, 0, 1) 5048
(3, 2, 1, 0) 4996
为了简单起见，我选择此算法，此演示文稿 [2] 简要概述了其他想法。
参考资料：
这样的排列称为紊乱。 在实践中，你可以尝试随机排列，直到出现混乱，随着“n”的增长，它们的比率接近“e”的倒数。
作为一个可能的起点，费舍尔-耶茨洗牌是这样的。
def swap(xs, a, b):
xs[a], xs[b] = xs[b], xs[a]
def permute(xs):
for a in xrange(len(xs)):
b = random.choice(xrange(a, len(xs)))
swap(xs, a, b)
也许这可以解决问题？
def derange(xs):
for a in xrange(len(xs) - 1):
b = random.choice(xrange(a + 1, len(xs) - 1))
swap(xs, a, b)
swap(len(xs) - 1, random.choice(xrange(n - 1))
这是 Vatine 描述的版本：
def derange(xs):
for a in xrange(1, len(xs)):
b = random.choice(xrange(0, a))
swap(xs, a, b)
return xs
快速统计测试：
from collections import Counter
def test(n):
derangements = (tuple(derange(range(n))) for _ in xrange(10000))
for k,v in Counter(derangements).iteritems():
print('{} {}').format(k, v)
test(4)(1, 3, 0, 2) 1665
(2, 0, 3, 1) 1702
(3, 2, 0, 1) 1636
(1, 2, 3, 0) 1632
(3, 0, 1, 2) 1694
(2, 3, 1, 0) 1671
这在其范围内确实看起来是均匀的，并且它具有一个很好的属性，即每个元素都有平等的机会出现在每个允许的插槽中。
但不幸的是它并没有包括所有的混乱。大小为 4 的排列有 9 种。（n=4 的公式和示例在维基百科文章中给出）。
这应该有效
import random
totalrandom = False
array = [1, 2, 3, 4]
it = 0
while totalrandom == False:
it += 1
shuffledArray = sorted(array, key=lambda k: random.random())
total = 0
for i in array:
if array[i-1] != shuffledArray[i-1]: total += 1
if total == 4:
totalrandom = True
if it > 10*len(array):
print("'Total random' shuffle impossible")
exit()
print(shuffledArray)
注意变量
it编辑
事实证明，如果您将其与大型数组（大于 15 个左右）一起使用，它将占用 CPU 资源。使用随机生成的 100 个元素数组并将其提高到
len(array)**3编辑2
大约 1200 秒（20 分钟）后，程序结束并提示“不可能进行完全随机洗牌”。对于大型数组，您需要大量的排列...比如 len(array)**10 之类的。
代码：
import random, time
totalrandom = False
array = []
it = 0
for i in range(1, 100):
array.append(random.randint(1, 6))
start = time.time()
while totalrandom == False:
it += 1
shuffledArray = sorted(array, key=lambda k: random.random())
total = 0
for i in array:
if array[i-1] != shuffledArray[i-1]: total += 1
if total == 4:
totalrandom = True
if it > len(array)**3:
end = time.time()
print(end-start)
print("'Total random' shuffle impossible")
exit()
end = time.time()
print(end-start)
print(shuffledArray)
这是一个较小的，具有 pythonic 语法 -
import random
def derange(s):
d=s[:]
while any([a==b for a,b in zip(d,s)]):random.shuffle(d)
return d
它所做的只是打乱列表，直到没有元素匹配为止。另外，请注意，如果传递了一个无法打乱的列表，它将永远运行。当存在重复时，就会发生这种情况。要删除重复项，只需调用如下函数即可
derange(list(set(my_list_to_be_deranged)))一个快速的方法是尝试重新排列列表，直到达到该状态。您只需尝试重新排列您的列表，直到留下满足您条件的列表。
import random
import copy
def is_derangement(l_original, l_proposal):
return all([l_original[i] != item for i, item in enumerate(l_proposal)])
l_original = [1, 2, 3, 4, 5]
l_proposal = copy.copy(l_original)
while not is_derangement(l_original, l_proposal):
random.shuffle(l_proposal)
print(l_proposal)
这是使用 pytorch 库的 python。
# typically input rp is the result of torch.randperm(torch.arange(N))
def derangement_(rp: torch.Tensor):
length = len(rp)
for i in range(0, length-1):
if (rp[i]==i):
rp[i],rp[(i+1)] = rp[(i+1)], rp[i]
# here rp[:length-1] must be a derangement
# therefore if rp[length-1] != (length-1) then rp is a derangement
if rp[length-1] == length-1:
rp[length-1],rp[0] = rp[0],rp[length-1]
# rp[0] == length-1
# rp[length-1] != length-1
# therefore rp is a derangement
# assert torch.all(rp != torch.arange(0,length))
return rp
代码注释中描述的证明
import random
a=[1,2,3,4]
c=[]
i=0
while i < len(a):
while 1:
k=random.choice(a)
#print k,a[i]
if k==a[i]:
pass
else:
if k not in c:
if i==len(a)-2:
if a[len(a)-1] not in c:
if k==a[len(a)-1]:
c.append(k)
break
else:
c.append(k)
break
else:
c.append(k)
break
i=i+1
print c