具有唯一值的排列

Question

具有唯一值的排列排列根据元素的位置而不是其值来生成元素被视为唯一的位置。所以基本上我想避免这样的重复：>>> 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.Products的输出太大。对不起，我应该描述一下实际的问题。

Answer 1

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrencesdef 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+=1a = 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 generatordef 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不同之处在于，每个元素不能重复更多次，即PER_UNIQUE_HELLER中的元素。

Answer 2

这依赖于实现细节，即排序迭代的任何排列都是按排序顺序排列的，除非它们是先前排列的重复。

from itertools import permutationsdef unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p            yield pfor 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')