python - 查找等于特定总和的列表部分排列的有效方法

Question

我有一组浮点值，我需要所有可能的排列，将它们加在一起，得到一个特定的数字。此外，我需要所有排列恰好包含八个值。

例如，我有以下一组值:

[0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]

我需要获得 8 个元素加起来为 20 的所有排列。

有效的代码如下:

N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20

accum = 0

for i1 in N:
  accum += i1
  for i2 in N:
    accum += i2
    for i3 in N:
      accum += i3
      for i4 in N:
        accum += i4
        for i5 in N:
          accum += i5
          for i6 in N:
            accum += i6
            for i7 in N:
              accum += i7
              for i8 in N:
                accum += i8
                if accum > target:
                  accum -= i8
                  break
                elif accum == target:
                  print(i1, i2, i3, i4, i5, i6, i7, i8)
                  accum -= i8
                  break
                accum -= i8
              accum -= i7
            accum -= i6
          accum -= i5
        accum -= i4
      accum -= i3
    accum -= i2
  accum -= i1

部分结果如下:

0.5 0.5 0.5 0.5 0.5 0.5 2 15
0.5 0.5 0.5 0.5 0.5 0.5 15 2
0.5 0.5 0.5 0.5 0.5 1.5 1 15
0.5 0.5 0.5 0.5 0.5 1.5 15 1
0.5 0.5 0.5 0.5 0.5 2 0.5 15
0.5 0.5 0.5 0.5 0.5 2 3 12.5
0.5 0.5 0.5 0.5 0.5 2 12.5 3
0.5 0.5 0.5 0.5 0.5 2 15 0.5
0.5 0.5 0.5 0.5 0.5 2.5 2.5 12.5
0.5 0.5 0.5 0.5 0.5 2.5 5 10
0.5 0.5 0.5 0.5 0.5 2.5 7.5 7.5
0.5 0.5 0.5 0.5 0.5 2.5 10 5
0.5 0.5 0.5 0.5 0.5 2.5 12.5 2.5
0.5 0.5 0.5 0.5 0.5 3 2 12.5

我可以稍后用 Excel 过滤结果。我不需要复杂的代码，我只需要最终的结果集。可以看出，这段代码效率极低，因为它需要花费大量时间来处理，并且还给出了大量的重复值。我没有深厚的编程知识，但我知道递归方法效率更高。我怎样才能得到我需要的结果？

Answer 1

这是一个递归解决方案。效率增益取决于:

• 在递归调用中，不要迭代整个列表，而只迭代列表的剩余部分。

• 无需从头开始对每个组合进行完全求和来测试它，只需在迭代时从目标中减去值即可。

在这种情况下，可以进一步提高效率，因为列表仅包含正数，因此如果特定值超出目标，则无需进行递归调用(elif val < target 测试)。如果没有这个事实，那部分代码将需要是无条件的，然后就会花费更长的时间。

测试用例在旧机器上花费了 0.04 秒。

def yield_combos(N, num, target):
    for i, val in enumerate(N):
        if num == 1:
            if val == target:
                yield [val]
        elif val < target:
            for j in yield_combos(N[i:], num - 1, target - val):
                yield [val] + j
    

N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20
num = 8
                    
for combo in yield_combos(N, num, target):
    print(f"combo={combo} length={len(combo)} total={sum(combo)}")

这给出:

combo=[0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 2, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 1, 1.5, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 7.5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 5, 5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1, 1, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1.5, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 7.5, 7.5] length=8 total=20.0
... etc ...

以上是在允许重复元素的基础上进行的。如果没有，则使用 N[i+1:]而不是N[i:]在递归调用中，尽管在这种情况下没有目标 20 的解决方案。

另请注意，这仅按照输入列表中索引递增的顺序给出每个解决方案(在本例中增加值，因为输入列表恰好已排序)，而不是它们的每个排列，基于额外排列的理解是问题暗示应该避免的“重复值”。但是，如果需要额外的排列，那么最有效的做法是最初完全按照上面的方式进行搜索(不在递归调用中循环遍历整个列表)，然后作为最后一步仅排列解决方案的元素。