具有唯一值的置换

2024-03-28 15:28:00 发布

您现在位置:Python中文网/ 问答频道 /正文

itertools.permutation根据元素的位置(而不是其值)生成其元素被视为唯一的位置。所以基本上我想避免这样的重复:

>>> 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的输出太大。

对不起,我应该描述一下实际的问题。


Tags: key算法元素编辑数量情况productpartial
3条回答

这依赖于实现细节,即排序的iterable的任何置换都是按排序的顺序排列的,除非它们是先前置换的副本。

from itertools import permutations

def unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p
            yield p

for p in unique_permutations('cabcab', 2):
    print p

给予

('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')
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表示置换辅助中的深度,有两个功能。一个函数是递归算法的停止条件,另一个函数是传递的结果列表。

我们不返回每个结果,而是放弃它。如果没有函数/运算符yield,我们将不得不在停止条件的某个点将结果推送到某个队列中。但是这样,一旦满足了停止条件,结果就会通过所有堆栈传播到调用方。这就是
for g in perm_unique_helper(listunique,result_list,d-1): yield g 所以每个结果都会传播到调用方。

回到原来的程序: 我们有一个独特元素的列表。在我们可以使用每个元素之前,我们必须检查有多少元素仍然可以推送到结果列表上。使用此程序与permutations_with_replacement非常相似。不同之处在于,每个元素的重复次数不能超过perm_unique_helper中的次数。

因为有时新问题会被标记为重复问题,并且它们的作者会被引用到这个问题中,所以必须指出sympy为此目的有一个迭代器。

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

相关问题 更多 >