Python分区函数

Question

我有以下代码，它是根据以前发布在该站点上的代码改编的。它是分区函数的一个变体，它输出所有可能的数字组合，这些组合加起来达到指定的总和，但它将可用于总和的数字限制在有限的输入列表中。

def part(nr, Nums):
    nrs = sorted(Nums, reverse=True)

    def inner(n, i):
        if n == 0:
            yield []
        for k in range(i, len(nrs)):
            if nrs[k] <= n:
                for rest in inner(n - nrs[k], k):
                    yield [nrs[k]] + rest

    return list(inner(nr, 0))


#List of numbers to form the sums.
Nums = [5,6 ,7 ,8, 9, 10]

#the total that the numbers add up to.
total = 32

tr = part(total, Nums)

print(f"{len(tr)}  Combination of {Nums} in {total} are:")
print(tr)

结果：

24 [5,6,7,8,9,10]在32中的组合是：

[[10, 10, 7, 5], [10, 10, 6, 6], [10, 9, 8, 5], [10, 9, 7, 6] , [10, 8, 8, 6], [10, 8, 7, 7], [10, 7, 5, 5, 5], [10, 6, 6, 5, 5], [9, 9, 9, 5], [9, 9, 8, 6], [9, 9, 7, 7], [9, 8, 8, 7], [9, 8, 5, 5, 5], [9, 7, 6, 5, 5], [9, 6, 6, 6, 5], [8, 8, 8, 8], [8, 8, 6, 5, 5], [8, 7, 7, 5, 5], [8, 7, 6, 6, 5], [8, 6, 6, 6, 6], [7, 7, 7, 6, 5], [7, 7, 6, 6, 6], [7, 5, 5, 5, 5, 5], [6, 6, 5, 5, 5, 5]]

进程已完成，退出代码为 0

一切都按预期工作，但我想更改它，以便每个数字只能使用一次或 none 在每个可能的组合中。

例如：“[10, 8, 7, 7], [10, 7, 5, 5, 5]”，这些组合和不会被输出，因为它们分别包含重复的七和五。

我试图保留生成器函数，因为有人告诉我它们比列表具有更好的性能，将来我可能会使用相同的函数来处理更大的列表和求和。但是我不确定如何检查生成器是否有重复数字以消除包含重复数字的子列表。

谢谢。

Answer 1

您可以将第 7 行更改为：for k in range(i + 1, len(nrs)):

Python分区函数

Python partition function

python

generator

partition