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

Question

我有一个包含重复元素的列表，即orig = [1,1,1,2,2,3]。
我想创建一个derangementb = f(orig)，这样b中的每个位置值都不同于{}中的值：

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

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

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

Answer 1

如果你的列表中有相当一部分是重复的，那么很难很快找到混乱。在

在这种情况下，您可以尝试图形方法。在

处理初始列表，生成一个图，其中每个项都与非相等元素连接（排序列表很容易）。在

然后构建完美匹配（若元素数为偶数）或近似完美匹配（对于奇数，这里需要找到合适的对并将单个节点连接到它）。在

匹配的边缘表示交换导致混乱。在

Python库networkx应该包含所需的方法。在

Answer 2

显然，不那么有效的解决方案是

import itertools
set([s for s in itertools.permutations(orig) if not any([a == b for a, b in zip(s, orig)])])

第二种方法和第一种改进是使用thisperm_unique：

^{pr2}$

第三种方法是使用这个超快速unique_permutationsalgorithm。在

 import copy
 [copy.copy(s) for s in unique_permutations(orig) if not any([a == b for a, b in zip(s, orig)])]

在我使用%%timeit的笔记本中，初始方法采用841 µs，我们改进为266 µs，然后改为{}。在

编辑

无法停止考虑，对第二种方法进行了小编辑。没有时间深入研究最后一种方法。有关解释，请先看原文（链接在上面）。然后我只添加了一个检查and el != elements[depth]，它强制执行混乱的条件。这样我们就得到了50 µs的运行时间。在

from collections import Counter

def derangement_unique(elements):
    list_unique = Counter(elements)
    length_list = len(elements)  # will become depth in the next function
    placeholder = [0]*length_list  # will contain the result
    return derangement_unique_helper(elements, list_unique, placeholder, length_list-1)

def derangement_unique_helper(elements, list_unique, result_list, depth):
    if depth < 0:   # arrived at a solution
        yield tuple(result_list)
    else:
        # consider all elements and how many times they should still occur 
        for el, count in list_unique.items():
            # ... still required and not breaking the derangement requirement
            if count > 0 and el != elements[depth]:   
                result_list[depth] = el  # assignment element
                list_unique[el] -= 1   # substract number needed
                # loop for all possible continuations 
                for g in derangement_unique_helper(elements, list_unique, result_list, depth-1):
                    yield g
                list_unique[el] += 1


list(derangement_unique(orig))