生成一个列表的随机错位排列

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

我不知道这种排列的正确术语（是"全排列"吗？）因此在谷歌搜索时很困难。 正确的术语似乎是“错排”。

- georg

---

请注意，这并不是完全随机的洗牌。 - Paddy

在stackoverflow上有一个类似的问题-> https://dev59.com/FWw05IYBdhLWcg3wXQwh但是回答者说：“我的算法实际上很糟糕：你仍然有可能最后一个点未被洗牌。”希望这可以帮助您指向正确的方向。 - Mathias

[1,1,2,3]怎么办？只需要“完全”洗牌索引，还是算法也应该考虑值呢？ - Kijewski

@OllieFord：我的意思是，该算法应随机生成一个“好”的排列之一。 - georg

@RafałDowgird：你漏掉了“随机”的点。 - georg

Answer 1

经过一些研究，我成功地实现了“提前拒绝”算法，就像这篇论文[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 Proceedings, 2007。
• [2] 生成随机错排。Martínez, Panholzer, Prodinger。

- georg

---

我冒昧地添加了对您提供的论文和演示文稿的明确引用，以便在链接失效时仍然可以找到它们。 - Stef

Answer 2

这种排列被称为错排。在实际应用中，您可以随机尝试排列，直到遇到一个错排，它们的比率会随着'n'的增长趋近于'e'的倒数。

- Rafał Dowgird

---

谢谢！“derangement”是我正在寻找的词。 - georg

我认为这里的其他答案（包括我的）都没有解决问题 - 这应该是被接受的答案。 - Chris Martin

我尝试了这个（例如 while 1: shuffle(a); if is_derangement(a) return a），不幸的是，结果分布不均匀。 - georg

@georg 你能扩展一下吗？如果 shuffle() 在排列中提供均匀分布，则从 shuffle() 的输出中选择错排（或其他任何集合）必须在错排（或其他任何集合）上提供均匀分布。 - Rafał Dowgird

@RafałDowgird：可能是我的测试有点问题。无论如何，“早期故障”算法是这种方法的一个合理优化，对我来说效果非常好。 - georg

Answer 3

作为一个可能的起点，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)

测试（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的示例在维基百科文章中给出)。

- Chris Martin

---

我认为这会存在“索引溢出”或“不触及最后一个元素”的风险。 - Vatine

嗯，你说得对。已经修复了索引问题，但最后一个元素可能仍然保持不变。 - Chris Martin

再编辑一次 - 这个有机会吗？虽然我现在太累了，不想算数。 - Chris Martin

Quick说“可能是这样的”。显然，经典的Fisher-Yates算法（你实现的“均匀洗牌算法”，尽管在列表的“已传递”部分进行交换），从索引1开始，选择“小于当前索引”的位置进行交换，可以保证所有元素最终处于不同的位置，而你的第二个算法似乎也是这样做的，但是针对数组的“尾”部分。 - Vatine

再次更新。我的版本不起作用（出现与之前相同的索引溢出问题，只是最后一个元素变成了倒数第二个）。而你的版本（假设我实现正确）并没有生成所有可能的错排。 - Chris Martin

Answer 4

这应该可以工作。

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)

- Beta Decay

---

换句话说，尝试生成排列，直到找到正确的一个。这可能有效，但我有点担心性能问题（我的列表有100多个元素）。 - georg

@georg 是的，我刚刚自己测试了一下... 我认为Chris Martin的答案可能是最好的。 - Beta Decay

Answer 5

这是一个较小的示例，具有Pythonic语法 -

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)))。

- Gurupad Mamadapur

---

但这可能需要很长时间！ - Kai

Answer 6

一个快速的方法是尝试对列表进行洗牌，直到达到所需状态。你只需要不断地对列表进行洗牌，直到得到满足条件的列表即可。

import random
import copy


def is_derangement(l_original, l_proposal):
    return all([l_original[i] != item for i, item in enumerate(l_proposal)])


l_original = [1, 2, 3, 4, 5]
l_proposal = copy.copy(l_original)

while not is_derangement(l_original, l_proposal):
    random.shuffle(l_proposal)

print(l_proposal)

- Rafael

Answer 7

import random
a=[1,2,3,4]
c=[]
i=0
while i < len(a):
    while 1:
     k=random.choice(a)
     #print k,a[i]
     if k==a[i]:
         pass
     else:
         if k not in c:
             if i==len(a)-2:
                 if a[len(a)-1] not in c:
                     if k==a[len(a)-1]:
                         c.append(k)
                         break
                 else:
                     c.append(k)
                     break
             else:
                 c.append(k)
                 break
    i=i+1
print c

- vks

---

我不明白你的代码是做什么的。能否加上注释说明一下？ - georg

这里我从输入列表中选择了一个随机元素。然后我检查它是否已经在新列表中。如果不是，则我检查它是否等于索引处的d元素。如果不是，那么我就要加入一个条件来检查它是否像312这样的条件，而最后一位必须是4，但这种情况不应该出现在d答案中。所以我排除了这种情况。 - vks

我刚刚进行了测试（请参见我的答案中的测试函数）。分布不是均匀的。 - Chris Martin

它包含所有的安排，对此不一致的原因我想不出来 :( - vks