具有唯一值的排列 [英] permutations with unique values

问题描述

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

itertools.permutations generates where its elements are treated as unique based on their position, not on their value. So basically I want to avoid duplicates like this:

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

由于我的排列量太大，因此无法进行后续过滤.

Filtering afterwards is not possible because the amount of permutations is too large in my case.

有人知道合适的算法吗?

Does anybody know of a suitable algorithm for this?

非常感谢！

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

What I basically want is the following:

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

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

which is not possible because sorted creates a list and the output of itertools.product is too large.

对不起，我应该已经描述了实际的问题.

Sorry, I should have described the actual problem.

推荐答案

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

编辑(这是如何工作的):

EDIT (how this works):

我改写了上面的程序，使它更长，但可读性更好.

I rewrote the above program to be longer but more readable.

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

I usually have a hard time explaining how something works, but let me try. In order to understand how this works, you have to understand a similar but simpler program that would yield all permutations with repetitions.

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并具有两个功能.一个函数是递归算法的停止条件，另一个函数是传递的结果列表.

This program is obviously much simpler: d stands for depth in permutations_helper and has two functions. One function is the stopping condition of our recursive algorithm, and the other is for the result list that is passed around.

我们产生而不是返回每个结果.如果没有函数/运算符yield，则必须在停止条件时将结果推送到某个队列中.但是这样一来，一旦满足停止条件，结果就会通过所有堆栈传播到调用者.那是
的目的 for g in perm_unique_helper(listunique,result_list,d-1): yield g 因此每个结果都会传播给调用者.

Instead of returning each result, we yield it. If there were no function/operator yield we would have to push the result in some queue at the point of the stopping condition. But this way, once the stopping condition is met, the result is propagated through all stacks up to the caller. That is the purpose of
for g in perm_unique_helper(listunique,result_list,d-1): yield g so each result is propagated up to caller.

返回原始程序: 我们有一个独特的元素列表.在使用每个元素之前，我们必须检查仍有多少个元素可以推送到result_list上.使用此程序与permutations_with_replacement非常相似.区别在于，每个元素的重复次数不能超过perm_unique_helper中的重复次数.

Back to the original program: we have a list of unique elements. Before we can use each element, we have to check how many of them are still available to push onto result_list. Working with this program is very similar to permutations_with_replacement. The difference is that each element cannot be repeated more times than it is in perm_unique_helper.

这篇关于具有唯一值的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！