python - 生成列表的随机排列

Question

我怎样才能随机打乱列表，使所有元素都不会留在原来的位置？

换句话说，给定一个包含不同元素的列表 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

我不知道这种排列的正确术语(是“总”吗？)因此很难用谷歌搜索。正确的术语似乎是“紊乱”。

Answer 1

经过一些研究，我能够实现“提前拒绝”算法，例如在 this paper .它是这样的:

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

为了简单起见，我选择了这个算法，this presentation简要概述了其他想法。