唯一值的排列

Question

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

抱歉，我应该更清楚地描述实际的问题。

Answer 1

这段话的意思是，任何一个已经排好序的列表，如果你把里面的元素顺序换一下，只要没有重复的元素，换完顺序后仍然是排好序的。

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

Answer 2

因为有时候新提问会被标记为重复问题，提问者会被引导到这个问题，所以提到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]]

Answer 3

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中的深度，里面有两个功能。一个功能是我们递归算法的停止条件，另一个是用于传递的结果列表。

我们不是返回每个结果，而是“产出”它。如果没有yield这个功能，我们就得在停止条件处把结果放到某个队列里。但这样一来，一旦满足停止条件，结果就会通过所有的调用栈传递回去。这就是
for g in perm_unique_helper(listunique,result_list,d-1): yield g的目的，让每个结果都能传递回去。

回到原来的程序：我们有一个独特元素的列表。在使用每个元素之前，我们得检查还有多少个可以放到结果列表里。使用这个程序的方式和permutations_with_replacement非常相似。不同之处在于，每个元素不能被重复使用超过它在perm_unique_helper中的数量。