生成列表的随机错位排列
我想知道怎么把一个列表随机打乱，确保里面的每个元素都不在原来的位置上。
换句话说，给定一个包含不同元素的列表A，我想生成一个新的列表B，满足以下条件：
- 这个新列表是随机的
- 并且对于每个位置
n，a[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
我不知道这种排列的正确术语（是不是叫“完全”呢？）所以在网上查找时有点困难。 正确的术语似乎是“错位排列”。
7 个回答
这里有一个更小的例子，语法很简洁 -
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
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，它会在调用的循环次数太多时退出代码。这是为了处理像 [1, 1, 1] 或 [3] 这样的数组。
编辑
结果发现，如果你用这个方法处理大数组（大于15个元素），会很耗费CPU资源。用一个随机生成的100个元素的数组，并把它的计算量提高到 len(array)**3，我的三星Galaxy S4花了很长时间才解决。
编辑 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)
作为一个可能的起点，Fisher-Yates 洗牌算法是这样的。
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 的公式和示例可以在维基百科文章中找到。）
这种排列叫做“错位排列”。实际上，你可以随便尝试一些随机的排列，直到找到一个错位排列为止。随着数字‘n’的增大，这些错位排列的比例会接近‘e’的倒数。
经过一些研究，我成功实现了“提前拒绝”算法，具体内容可以参考这篇论文 [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]简要介绍了其他的一些思路。
参考文献：
- [1] 一种简单算法生成随机错位排列的分析。Merlini, Sprugnoli, Verri. WSPC 会议论文，2007年。
- [2] 生成随机错位排列。Martínez, Panholzer, Prodinger。