如何计算具有重复元素的列表的混乱（排列）

Question

我有一个包含重复元素的列表，即orig = [1,1,1,2,2,3].
我想创建一个混乱 b = f(orig)，以便对于每个位置值 inb都不同于值 in orig：

b[i] != orig[i], for all i

当所有元素orig都是唯一的时，我知道一个解决方案，但这是一个更难的情况。

用 python 开发解决方案，但任何语言都可以。

Answer 1

如果您的列表包含大量重复项，则可能很难快速找到混乱。在这种情况下，您可以尝试图形方法。处理初始列表以制作一个图形，其中每个项目都与不相等的元素相连（易于排序列表）。然后建立完美匹配（如果元素数量是偶数）或接近完美匹配（对于奇数，您需要找到一些合适的配对并将单个节点加入它）。匹配的边缘表示交换使混乱。Python 库networkx应该包含所需的方法。