查找具有目标总和的不同子列表-解网

问：

我目前正在处理一项任务，该任务涉及从给定列表中识别不同的子列表，以便每个子列表加起来为指定的目标编号之一。

下面是我为解决此问题而编写的 Python 代码。此递归函数中的主要方法包括迭代地从列表中删除元素，并将它们分配给与目标编号之一相对应的子列表或丢弃它们。当找到解决方案并输出结果时，或者由于列表为空或其中一个子列表中的超调而无法完成时，该函数将终止。

def subset_sums(numbers, target_array, total_partial=None, partial_sum=None):
    # If it's the first function call, initialize partial_sum and enumerate numbers to detect duplicates
    if partial_sum is None:
        numbers = [(v, i) for i, v in enumerate(numbers)]
        total_partial = [[] for _ in range(len(target_array))]
        partial_sum = np.zeros(len(target_array))

    # If all sublists have the correct sum, yield the resulting sublists
    if (target_array == partial_sum).all():
        yield total_partial
        return

    # If we don't reach a correct result and have no numbers left, stop the function
    elif not numbers:
        return

    # Get the next number and the remaining list
    n_with_index = numbers[0]
    n = n_with_index[0]
    remaining = numbers[1:]

    # Case 1: Skip the new number and continue with the rest of the numbers
    yield from subset_sums(remaining, target_array, total_partial, partial_sum)

    # Case 2: Use the new number for each possible list
    for j in range(len(target_array)):
        # If using the new number would overshoot in that list, stop
        if (partial_sum[j] + n) > target_array[j]:
            return
        # Otherwise, use the new number and continue with the rest of the numbers
        else:
            next_total_partial = total_partial
            next_total_partial[j] = next_total_partial[j] + [n_with_index]
            next_partial_sum = partial_sum
            next_partial_sum[j] = next_partial_sum[j] + n
            yield from subset_sums(remaining, target_array, next_total_partial, next_partial_sum)

但是，我在代码中遇到了一个似乎无法解决的持续缺陷。问题在于，同一个列表元素被追加到不同的子列表，并且算法无法按预期排除列表元素。我已经彻底审查了代码，但我无法确定为什么这个问题仍然存在。

以下代码片段显示了一个示例实例：

In [1]: list(subset_sums2([1,3,1,3], np.array([3,5])))
Out[1]: []

但是，我希望输出：

Out[1]: [
    [[(3, 1)], [(1, 0), (1, 2), (3, 3)]], # target 3 is the 3 at index 1; target 5 is the sum of all other numbers 
    [[(3, 3)], [(1, 0), (1, 2), (3, 1)]]] # target 3 is the 3 at index 3; target 5 is the sum of all other numbers

请注意，输出是（value， index）对。在这里，我们有两种方法可以获得 3 和 5 的目标数字：它们是相同的，只是给定的 3 用于实现 3 目标与 5 目标。

我将不胜感激任何能够帮助我识别和纠正实施过程中的问题的帮助。提前感谢您的帮助:)

Python 算法数学排列子列表

    for j in range(len(target_array)):
        # If using the new number would overshoot in that list, stop
        if (partial_sum[j] + n) > target_array[j]:
            return
        # Otherwise, use the new number and continue with the rest of the numbers
        else:
            next_total_partial = total_partial
            next_total_partial[j] = next_total_partial[j] + [n_with_index]
            next_partial_sum = partial_sum
            next_partial_sum[j] = next_partial_sum[j] + n
            yield from subset_sums(remaining, target_array, next_total_partial, next_partial_sum)

当使用您提供的示例调用函数时：

list(subset_sums([1,3,1,3], np.array([3,5])))

即使在第二次迭代中，也已经出现了问题。在第一次迭代中，设置为，然后在下一行更新。但这会修改和，因为它们具有相同的值。next_total_partialtotal_partialnext_total_partialtotal_partialnext_total_partial

因此，在第二次迭代中，您认为重置为：next_total_partial

            next_total_partial = total_partial

但实际上，没有任何变化 - 它仍然具有与值相同的对象，并且您现在将相同的值（在本例中）添加到和。(3, 3)next_total_partialtotal_partial

也许你想要？当然，这同样适用。next_total_partial = total_partial.copy()next_partial_sum = partial_sum.copy()

可以修复您的逻辑以使其工作，但这不是一种非常有效的方法，并且还有其他一些问题：

主要问题是我指出的：你在需要副本的地方传递相同的对象
你有一个递归函数，但你也用它来初始化 - 这对于辅助外部函数或内部函数会更好
当有更有效的方法来实现这一目标时，您正在暴力破解解决方案

一个工作解决方案的示例，该解决方案修复了一些问题，但具有与你选择的方法相同的方法：

from copy import deepcopy


def find_sums(target_sums, xs):
    def _all_sums(enumerated_xs, sums, grouping):
        if not enumerated_xs:
            yield grouping
            return

        i, v = enumerated_xs[0]
        for j in range(len(sums)):
            if sums[j] + v <= target_sums[j]:
                new_grouping = deepcopy(grouping)
                new_grouping[j] += [(i, v)]
                yield from _all_sums(enumerated_xs[1:], sums[:j] + [sums[j] + v] + sums[j+1:], new_grouping)

    if sum(target_sums) != sum(xs):
        return

    yield from _all_sums(list(enumerate(xs)), [0]*len(target_sums), [[] for _ in range(len(target_sums))])


print(list(find_sums([3, 5], [1, 3, 1, 3])))

甚至更接近，也许更适合你：

from copy import deepcopy


def find_sums(target_sums, xs):
    def _all_sums(enumerated_xs, sums, grouping):
        if not enumerated_xs:
            yield grouping
            return

        i, v = enumerated_xs[0]
        for j in range(len(sums)):
            if sums[j] + v <= target_sums[j]:
                new_grouping = deepcopy(grouping)
                new_grouping[j] += [(i, v)]
                new_sums = sums.copy()
                new_sums[j] += v
                yield from _all_sums(enumerated_xs[1:], new_sums, new_grouping)

    if sum(target_sums) != sum(xs):
        return

    yield from _all_sums(list(enumerate(xs)), [0]*len(target_sums), [[] for _ in range(len(target_sums))])


print(list(find_sums([3, 5], [1, 3, 1, 3])))

感谢您的全面回复！我不得不对您的代码进行一些小的调整，以适应某些数字可能对生成的子列表没有贡献的情况。你的解决方案澄清了我的误解。我最初认为递归函数调用会自动复制变量。这种误解源于这样一个事实，即使用像 sums[：j] + [sums[j] + v] + sums[j+1：] 这样的变量变体确实会创建一个新变量，不是吗？

1赞 Grismar 11/16/2023

是的，构造一个新列表并将该值分配给另一个变量（我是这样表述的）可以避免这个问题。创建列表副本的一种简单方法是 - 示例中的构造也替换了相关索引处的值。使用可以达到相同的效果，但需要在之后进行替换。如果您觉得这回答了您的问题，请考虑单击它旁边的复选标记，以便您的问题不再显示为未回答。xsxs_copy = xs[:].copy()

0赞 mathbreaker 11/16/2023

是的，这完全回答了我的问题。谢谢！

上一个：解码 XOR 排列的结果总是唯一的，这是真的吗？

下一个：如何使用排列在 Java 中使用自定义迭代器向后迭代

查找具有目标总和的不同子列表

Finding Distinct Sublists with Target Sums

评论

评论