Python-具有唯一值的排列

  • Z时代
  • 2024-01-10
  • 分类：问答

itertools.permutations会根据其位置而不是其值来生成其元素被视为唯一的元素。所以基本上我想避免重复这样的事情：

>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]

之后的过滤是不可能的，因为在我的情况下，排列的数量太大。

有人知道合适的算法吗？

非常感谢你！

编辑：

我基本上想要的是以下内容：

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

这是不可能的，因为sorted创建列表并且itertools.product的输出太大。

抱歉，我应该已经描述了实际问题。

回答：

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences
def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)
def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1
a = list(perm_unique([1,1,2]))
print(a)

结果：

[(2, 1, 1), (1, 2, 1), (1, 1, 2)]

编辑（这是如何工作的）：

我将上面的程序改写得更长，但可读性更好。

我通常很难解释一些事情，但是让我尝试一下。为了理解它是如何工作的，你必须了解一个类似但更简单的程序，该程序将产生所有带有重复的排列。

def permutations_with_replacement(elements,n):
    return permutations_helper(elements,[0]*n,n-1)#this is generator
def permutations_helper(elements,result_list,d):
    if d<0:
        yield tuple(result_list)
    else:
        for i in elements:
            result_list[d]=i
            all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
            for g in all_permutations:
                yield g

这个程序显然要简单得多：d代表permutations_helper中的depth并具有两个功能。一个函数是递归算法的停止条件，另一个函数用于传递的结果列表。

我们不返回每个结果，而是产生它。如果没有功能/运算符，yield我们将不得不在停止条件时将结果推送到某个队列中。但是这样一来，一旦满足停止条件，结果就会通过所有堆栈传播到调用者。这样做的目的是

for g in perm_unique_helper(listunique,result_list,d-1): yield g使每个结果都传播给调用方。

回到原始程序：我们有一个唯一元素列表。在使用每个元素之前，我们必须检查仍有多少个元素可以推送到result_list上。使用此程序非常类似于permutations_with_replacement。不同之处在于，每个元素的重复次数不能超过perm_unique_helper中的重复次数。

以上是 Python-具有唯一值的排列 的全部内容， 来源链接： utcz.com/qa/412789.html

回到顶部