生成包含重复元素的列表的r长度排列 Python

Question

我的问题跟这里提到的那个问题有点相似。不过，我需要的是一个可以生成包含重复元素的列表的r元组排列的算法。

举个例子：

list1 = [1,1,1,2,2]

for i in permu(list1, 3):
     print i 

[1,1,1]
[1,1,2]
[1,2,1]
[2,1,1]
[1,2,2]
[2,1,2]
[2,2,1]

看起来itertools.permutations可以用得很好，只需要加个简单的过滤步骤来去掉重复的结果。不过在我的实际情况中，列表比这个例子要长得多，正如你所知道的，itertools.permutations的复杂度随着列表长度的增加而呈指数增长。

到目前为止，我写的代码如下。这段代码能完成我想要的功能，但效率不高。

def generate_paths(paths, N = None):
    groupdxs = [i for i, group in enumerate(paths) for _ in range(len(group))]
    oldCombo = []
    result = []
    for dxCombo in itertools.permutations(groupdxs, N):
        if dxCombo <= oldCombo: # as simple filter
            continue
        oldCombo = dxCombo
        parNumbers = partialCombinations(dxCombo, len(paths))
        if not parNumbers.count(0) >= len(paths)-1: # all of nodes are coming from same path, same graph 
            groupTemps = []
            for groupInd in range(len(parNumbers)):
                groupTemp = [x for x in itertools.combinations(paths[groupInd], parNumbers[groupInd])]
                groupTemps.append(groupTemp)
            for parGroups in itertools.product(*groupTemps):
                iters = [iter(group) for group in parGroups]
                p =  [next(iters[i]) for i in dxCombo]
                result.append(p)
    return result


def partialCombinations(combo, numGruops):
    tempCombo = list(combo)
    result = list([0] * numGruops)
    for x in tempCombo:
        result[x] += 1
    return result

在第一个for循环中，我需要生成所有可能的r长度的元组，这让算法变得很慢。上面链接中有一个不使用r长度的排列的好解决方案。我该如何把这个算法改成适合我的呢？或者有没有更好的方法？

Answer 1

我对你的情况没有想得很透彻，但我可以给你提供另一种思路。

与其给很长的列表去计算排列，不如给一个没有重复项的小列表。你可以使用组合（带替换）的方法来生成这些较小的列表（你需要过滤一下，以确保它们的重复数量和你原始输入的一样），然后再对每个组合进行排列。

possible_values = (1,2)
n_positions = 3

sorted_combinations = itertools.combinations_with_replacement(possible_values, n_positions)
unique_permutations = set()
for combo in sorted_combinations:
    # TODO: Do filtering for acceptable combinations before passing to permutations.
    for p in itertools.permutations(combo):
        unique_permutations.add(p)


print "len(unique_permutations) = %i. It should be %i^%i = %i.\nPermutations:" % (len(unique_permutations), len(possible_values), n_positions, pow(len(possible_values), n_positions))
for p in unique_permutations:
    print p