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

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

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

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

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

最佳答案

不太有效的解决方案显然是

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 µs。

编辑

不能停止考虑，对第二种方法进行了少量编辑。没有时间去研究最后一种方法。有关说明，请先参阅原始帖子（上面的链接）。然后，我只添加了强制的检查条件，以强制发生混乱。这样，我们得出的运行时间为and el != elements[depth]。

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

关于python - 如何计算具有重复元素的列表的排列(排列)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52854146/