python - 如何计算具有重复元素的列表的排列(排列)

Question

我有一个包含重复元素的列表，即orig = [1,1,1,2,2,3]。
我想创建一个derangement b = f(orig)，使得 b 中的每个位置值都与 orig 中的值不同:

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

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

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

Answer 1

显然，效率不高的解决方案

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

第二种方法和第一个改进是使用 this perm_unique:

 [s for s in perm_unique(orig) if not any([a == b for a, b in zip(s, orig)])]

第三种方法是使用这种超快速的unique_permutations algorithm 。

 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，然后改进为 137 微秒。

编辑

无法停止考虑，对第二种方法进行了小修改。没有时间深入研究最后一种方法。有关解释，请首先查看原始帖子(上面的链接)。然后我只添加了检查 和 el != elements[深度] ，这强制了困惑的条件。这样我们就得到了 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))