生成列表的随机排列

问题内容：

如何随机排列列表，以使所有元素均不保留其原始位置？

换句话说，给定一个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

~~我不知道这种排列的正确用语（是否是“总计”？），因此很难进行谷歌搜索。~~ 正确的词似乎是“混乱”。

问题答案：

经过一些研究，我能够实现如本文所述的“早期拒绝”算法。它是这样的：

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

为了简单起见，我选择此算法，本演示文稿简要概述了其他想法。

生成列表的随机排列

微信关注