保证洗牌列表

Question

给定一个列表/有序集合，有没有办法对其成员进行保证改组/重新排序（意味着没有元素与之前的位置相同），而无需求助于反复试验？我在这里使用 python，但这显然适用于具有这种结构的任何语言。

例如，如果我有一个列表 l = [1, 2, 3, 4, 5] 并随机打乱它：

import random                                                                                                                                                                                                                                                                                                                             

for _ in range(5): 
    random.shuffle([1,2,3,4,5]); 
    print(l) 
[1, 2, 3, 5, 4] # 1,2,3
[2, 4, 3, 1, 5] # 3, 5
[2, 1, 4, 5, 3] # OK!
[2, 5, 3, 1, 4] # 3
[5, 3, 4, 2, 1] # OK!

可以看到只有第3和第4输出的所有元素确实在列表中的不同位置，而其他情况我都写了保持在相同位置的列表元素。

更体贴的方法，例如在每个位置省略违规元素：

l=[1,2,3,4,5]
shuffled = []
for i in l:
    sample_from = [x for x in l if x not in shuffled + [i]]
    try:
        shuffled.append(random.sample(sample_from, 1)[0])
    except:
        print("Attempted to sample from", sample_from)
        break
    print("Shuffled portion:", shuffled)

可能会导致没有可行解决方案的错误，例如：

Shuffled portion: [2]
Shuffled portion: [2, 4]
Shuffled portion: [2, 4, 1]
Shuffled portion: [2, 4, 1, 3]
Attempted to sample from []

其中5刚好留到最后，没有其他位置可以替代原来的位置。我想当到达这个位置时，我可以将剩余的 5 与随机列表中的任何元素交换。

但是，有没有其他更简单、更漂亮的算法方法可以在没有此类手动破解的情况下实现这一目标？谢谢！

Answer 1

要生成混乱，您可以使用 Fisher-Yates 混洗算法，并且在选择要交换的索引时将当前索引排除在考虑范围之外（即，不允许将元素与其自身交换）。

保证洗牌列表

Guaranteed shuffling of a list

python

shuffle

list

reorderlist