<pre><code>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)
</code></pre>
<p>结果:</p>
<pre><code>[(2, 1, 1), (1, 2, 1), (1, 1, 2)]
</code></pre>
<p>编辑(工作原理):</p>
<p>我重写了上面的程序,使其更长但可读性更强。</p>
<p>我通常很难解释某事是如何工作的,但让我试试。
为了理解这是如何工作的,您必须理解一个类似但更简单的程序,该程序将产生具有重复的所有排列。</p>
<pre><code>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
</code></pre>
<p>这个程序显然要简单得多:
d表示置换辅助中的深度,有两个功能。一个函数是递归算法的停止条件,另一个函数是传递的结果列表。</p>
<p>我们不返回每个结果,而是放弃它。如果没有函数/运算符<code>yield</code>,我们将不得不在停止条件的某个点将结果推送到某个队列中。但是这样,一旦满足了停止条件,结果就会通过所有堆栈传播到调用方。这就是<br/>
<code>for g in perm_unique_helper(listunique,result_list,d-1): yield g</code>
所以每个结果都会传播到调用方。</p>
<p>回到原来的程序:
我们有一个独特元素的列表。在我们可以使用每个元素之前,我们必须检查有多少元素仍然可以推送到结果列表上。使用此程序与<code>permutations_with_replacement</code>非常相似。不同之处在于,每个元素的重复次数不能超过perm_unique_helper中的次数。</p>