生成列表的随机紊乱

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

这种排列称为紊乱.在实践中,您可以尝试随机排列直到达到紊乱,当'n'增长时,它们的比率接近'e'的倒数.

Answer 2

经过一些研究后,我能够实现"早期拒绝"算法,如本文所述.它是这样的:

import random

def random_derangement(n):
    while True:
        v = 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

为简单起见,我选择此算法,此简要介绍了其他想法.

感谢大家 ))