一个函数来查找所有组合而不重复，加起来是一个数字

Question

我正在寻找一个函数，它可以从总和为一个数字的列表中找到所有唯一的组合。我不能把列表的所有排列都扔掉，因为列表会很长而且时间很重要。

the_list = [7,6,5,5,4,3,2,1] stop_sum = 11

因此，如果找到组合 (7, 3, 1)，我不想找到 (1, 3, 7)。

目前我正在使用类似 down under 的递归函数来完成它，但是当列表包含 300 多个数字时这还不够。（所有整数）。

the_list = [7,6,5,5,4,3,2,1]
stop_sum = 11

unique_combos = []
def combo_find(C, S, B=[]):

    for i, a in enumerate(C):

        if a > S:
            continue

        B.append(a) # B+[a] can still be a possible list

        if a == S:  # Found a sequence that works

            sequence = sorted(tuple(B))
            if sequence not in unique_combos:
                unique_combos.append(sequence)

        combo_find(C[i + 1:], S - a, B)
        B.pop()  # drop [a] from possible list

the_list.sort()
combo_find(the_list, stop_sum)
print(unique_combos)

有人知道如何以 smarter/faster 的方式做到这一点吗？

Answer 1

以下应该是合理的性能，使用一些缓存：

from functools import lru_cache

def combo_find(C, S):
    C.sort()

    @lru_cache(None)
    def rec(pool, s):
        if not s:
            return [[]]
        if s < 0:
            return []
        i, result = 0, []
        while i < len(pool):
            crnt = pool[i]
            for combo in rec(pool[i+1:], s-crnt):
                result.append([crnt] + combo)
            # use the first of consecutive equals or none of them!
            # this avoids duplicates, but allows using all occurrences without any membership tests
            while i < len(pool) and pool[i] == crnt:
                i += 1
        return result

    return rec(tuple(C), S)  # tuplify so the args are hashable

>>> combo_find([7,6,5,5,4,3,2,1], 11)
[[1, 2, 3, 5], [1, 3, 7], [1, 4, 6], [1, 5, 5], [2, 3, 6], [2, 4, 5], [4, 7], [5, 6]]

Answer 2

您可以将 solve 编写为数字 n 和查询总和 q 的函数。该算法不需要 n 进行排序，如果您有排序要求，可以对其进行优化。该算法使用 inductive reasoning -

编写

如果查询总和q为零，我们就已经知道答案了。产生空解 {} 和 return.
（归纳）q 不为零。如果 q 为负数或 n 没有剩余数字可检查，则解决方案越界或无法达到。 Return.
（归纳法）q 是正数，n 有 至少一个 数字要检查。对于子问题的每一个解，如果第一个 n 不存在于解中，则添加第一个，然后 yield。另外尝试通过跳过第一个 n.

q

def solve (n, q):
  # 1. solution found, return empty set
  if q == 0: return (yield set())
  # 2. solution out of bounds or no more nums to check
  if q < 0 or not n: return
  # 3. for each solution to sub-problem, if first n not in solution, add it
  for sln in solve(n[1:], q - n[0]):
    if n[0] not in sln:
      yield {n[0], *sln}
  # 3. and solve q skipping the first n
  yield from solve(n[1:], q)

the_list = [7,6,5,5,4,3,2,1]

for x in solve(the_list, 11):
  print(x)

{4, 7}
{1, 3, 7}
{5, 6}
{5, 6}
{1, 4, 6}
{2, 3, 6}
{2, 4, 5}
{1, 2, 3, 5}
{2, 4, 5}
{1, 2, 3, 5}

n可以任意顺序-

the_list = [2,1,5,3]

for x in solve(the_list, 8):
  print(x)

{1, 2, 5}
{3, 5}

如果找不到解决方案，您将得到一个空结果 -

print(list(solve([1,2,3], 99)))

[]

一个函数来查找所有组合而不重复，加起来是一个数字

A function to find all combinations without repetition that adds up to a number

python

recursion

combinations

function

permutation