生成列表的随机排列 [英] Generate a random derangement of a list

问题描述

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

How can I randomly shuffle a list so that none of the elements remains in its original position?

换句话说，给定具有不同元素的列表A，我想为其生成一个置换B，以便

In other words, given a list A with distinct elements, I'd like to generate a permutation B of it so that

• 此排列是随机的
• ，对于每个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

我不知道这种排列的正确用语(是否是总计"?)，因此很难进行谷歌搜索.正确的用语似乎是混乱".

I don't know the proper term for such a permutation (is it "total"?) thus having a hard time googling. The correct term appears to be "derangement".

推荐答案

经过一番研究，我得以实现提早拒绝"算法，例如在本文中.它是这样的:

After some research I was able to implement the "early refusal" algorithm as described e.g. in this paper. It goes like this:

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)，我们就会中断并从头开始.

The idea is: we keep shuffling the array, once we find that the permutation we're working on is not valid (v[i]==i), we break and start from scratch.

一项快速测试表明，该算法会统一生成所有排列错误:

A quick test shows that this algorithm generates all derangements uniformly:

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

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

I choose this algorithm for simplicity, this presentation briefly outlines other ideas.

谢谢大家))

这篇关于生成列表的随机排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！