不重复排列

Question

N = 14
SIZE = 6
lst = range(N+1) 
sum_n_combs = [
    list(comb) for comb in it.combinations_with_replacement(lst, SIZE)
    if sum(comb) == N
]
print(sum_n_combs)

output [[0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 1, 13], [0, 0, 0, 0, 2, 12], [0, 0, 0, 0, 3, 11], [0, 0, 0, 0, 4, 10], [0, 0, 0, 0, 5, 9], [0, 0, 0, 0, 6, 8], [0, 0, 0, 0, 7, 7], [0, 0, 0, 1, 1, 12], [0, 0, 0, 1, 2, 11], [0, 0, 0, 1, 3, 10], [0, 0, 0, 1, 4, 9], [0, 0, 0, 1, 5, 8], [0, 0, 0, 1, 6, 7], [0, 0, 0, 2, 2, 10], [0, 0, 0, 2, 3, 9], [0, 0, 0, 2, 4, 8], [0, 0, 0, 2, 5, 7], [0, 0, 0, 2, 6, 6], [0, 0, 0, 3, 3, 8], [0, 0, 0, 3, 4, 7], [0, 0, 0, 3, 5, 6], [0, 0, 0, 4, 4, 6], [0, 0, 0, 4, 5, 5], [0, 0, 1, 1, 1, 11], [0, 0, 1, 1, 2, 10], [0, 0, 1, 1, 3, 9], [0, 0, 1, 1, 4, 8], [0, 0, 1, 1, 5, 7], [0, 0, 1, 1, 6, 6], [0, 0, 1, 2, 2, 9], [0, 0, 1, 2, 3, 8], [0, 0, 1, 2, 4, 7], [0, 0, 1, 2, 5, 6], [0, 0, 1, 3, 3, 7], [0, 0, 1, 3, 4, 6], [0, 0, 1, 3, 5, 5], [0, 0, 1, 4, 4, 5], [0, 0, 2, 2, 2, 8], [0, 0, 2, 2, 3, 7], [0, 0, 2, 2, 4, 6], [0, 0, 2, 2, 5, 5], [0, 0, 2, 3, 3, 6], [0, 0, 2, 3, 4, 5], [0, 0, 2, 4, 4, 4], [0, 0, 3, 3, 3, 5], [0, 0, 3, 3, 4, 4], [0, 1, 1, 1, 1, 10], [0, 1, 1, 1, 2, 9], [0, 1, 1, 1, 3, 8], [0, 1, 1, 1, 4, 7], [0, 1, 1, 1, 5, 6], [0, 1, 1, 2, 2, 8], [0, 1, 1, 2, 3, 7], [0, 1, 1, 2, 4, 6], [0, 1, 1, 2, 5, 5], [0, 1, 1, 3, 3, 6], [0, 1, 1, 3, 4, 5], [0, 1, 1, 4, 4, 4], [0, 1, 2, 2, 2, 7], [0, 1, 2, 2, 3, 6], [0, 1, 2, 2, 4, 5], [0, 1, 2, 3, 3, 5], [0, 1, 2, 3, 4, 4], [0, 1, 3, 3, 3, 4], [0, 2, 2, 2, 2, 6], [0, 2, 2, 2, 3, 5], [0, 2, 2, 2, 4, 4], [0, 2, 2, 3, 3, 4], [0, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 5, 5], [1, 1, 1, 2, 2, 7], [1, 1, 1, 2, 3, 6], [1, 1, 1, 2, 4, 5], [1, 1, 1, 3, 3, 5], [1, 1, 1, 3, 4, 4], [1, 1, 2, 2, 2, 6], [1, 1, 2, 2, 3, 5], [1, 1, 2, 2, 4, 4], [1, 1, 2, 3, 3, 4], [1, 1, 3, 3, 3, 3], [1, 2, 2, 2, 2, 5], [1, 2, 2, 2, 3, 4], [1, 2, 2, 3, 3, 3], [2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 3, 3]]

与“带替换的组合”一样，此函数仅生成组合。我想要每个组合的排列而不重复。例如

[[0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 14, 0] ... [3, 2, 3, 2, 2, 2], [3, 3, 2, 2, 2]]

当我尝试这样做时

ret=[]
for i in range(90):
   ret.extend(it.permutations(sum_n_combs[i], SIZE))

时间复杂度呈指数级，重复当我用一个列表 sum_n_combs[0] 进行测试时，即 [0, 0, 0, 0, 0, 14] 产生了 720 个排列，而我只想要其中的 6 个（每个不同的地方 14 个）。

如何高效地对每个组合进行排列而不重复？

Answer 1

您可以将其分为两步：

生成目标总和的分区
为每个分区生成不同的排列

递归生成器将使您无需 trial/error 过滤且无需将所有内容存储在内存中即可高效地获得结果：

def partitions(N,size):
    if size == 1 :
        yield (N,)                            # base case, only 1 part
        return
    for a in range(N//size+1):                # smaller part followed by
        for p in partitions(N-a*size,size-1): # equal or larger ones
            yield (a, *(n+a for n in p))      # recursing on delta only

def permuteDistinct(A):
    if len(A) == 1:
        yield tuple(A) # single value
        return
    used = set()               # track starting value
    for i,n in enumerate(A):   # for each starting value
        if n in used: continue # not yet used
        used.add(n)
        for p in permuteDistinct(A[:i]+A[i+1:]): 
            yield (n,*p)       # starting value & rest

输出：

N    = 14
SIZE = 6

分区...

for part in partitions(N,SIZE):
    print(part)

(0, 0, 0, 0, 0, 14)
(0, 0, 0, 0, 1, 13)
(0, 0, 0, 0, 2, 12)
(0, 0, 0, 0, 3, 11)
(0, 0, 0, 0, 4, 10)
(0, 0, 0, 0, 5, 9)
(0, 0, 0, 0, 6, 8)
(0, 0, 0, 0, 7, 7)
(0, 0, 0, 1, 1, 12)
(0, 0, 0, 1, 2, 11)
(0, 0, 0, 1, 3, 10)
(0, 0, 0, 1, 4, 9)
(0, 0, 0, 1, 5, 8)
(0, 0, 0, 1, 6, 7)
(0, 0, 0, 2, 2, 10)
(0, 0, 0, 2, 3, 9)
(0, 0, 0, 2, 4, 8)
(0, 0, 0, 2, 5, 7)
(0, 0, 0, 2, 6, 6)
(0, 0, 0, 3, 3, 8)
(0, 0, 0, 3, 4, 7)
(0, 0, 0, 3, 5, 6)
(0, 0, 0, 4, 4, 6)
(0, 0, 0, 4, 5, 5)
...

置换分区（不同）：

for part in partitions(N,SIZE):
    for permutedPart in permuteDistinct(part):
        print(permutedPart)

(0, 0, 0, 0, 0, 14)
(0, 0, 0, 0, 14, 0)
(0, 0, 0, 14, 0, 0)
(0, 0, 14, 0, 0, 0)
(0, 14, 0, 0, 0, 0)
(14, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 13)
(0, 0, 0, 0, 13, 1)
(0, 0, 0, 1, 0, 13)
(0, 0, 0, 1, 13, 0)
(0, 0, 0, 13, 0, 1)
(0, 0, 0, 13, 1, 0)
(0, 0, 1, 0, 0, 13)
(0, 0, 1, 0, 13, 0)
(0, 0, 1, 13, 0, 0)
(0, 0, 13, 0, 0, 1)
(0, 0, 13, 0, 1, 0)
(0, 0, 13, 1, 0, 0)
...

不重复排列

permutation without repitition

python

combinations

permutation