查找列表中总和等于给定数字的不同部分

Question

我想从没有重复数字的输入列表中找到总和等于 K 的不同元组。

Input: A=[1, 2, 3], K = 3 
Output: 
(1, 2)
(2, 1)
(3) 

请注意 - (2,3) 与 (3,2) 不同。

我正在做什么：

def unique_combination(l, sum, K, local, A):
 
    # If a unique combination is found
    if (sum == K):
        print("(", end="")
        for i in range(len(local)):
            if (i != 0):
                print(" ", end="")
            print(local[i], end="")
            if (i != len(local) - 1):
                print(", ", end="")
        print(")")
        return
 
    # For all other combinations
    for i in range(l, len(A), 1):
 
        # Check if the sum exceeds K
        if (sum + A[i] > K):
            continue
 
        # Check if it is repeated or not
        if (i > l and
                A[i] == A[i - 1]):
            continue
 
        # Take the element into the combination
        local.append(A[i])
 
        # Recursive call
        unique_combination(i+1, sum + A[i],
                           K, local, A)
 
        # Remove element from the combination
        local.remove(local[len(local) - 1])
 

def myFunc(A, K):
 
    # Sort the given elements
    A.sort(reverse=False)
 
    local = []
 
    unique_combination(0, 0, K, local, A)
 

arr = [1,2,3,4,6,7]
target = 8
myFunc(arr, target)

这个函数返回：

Input: A=[1,2,3,4,6,7], K = 8 
Output: 
(1,  3,  4)
(1,  7)
(2,  6)

我还想要其他组合，例如： (1,4,3),(1,3,4),(4,1,3),(4,3,1),(3,1,4),(3,4,1),(7 , 1), (2, 6)

那么，我应该如何处理代码才能实现我的结果......

Answer 1

您原来的函数正在正确生成可能的组合。唯一的问题是您正在打印它，而不是将其保存在列表中以供以后使用。

我修改了它，以便将结果保存到一个列表中，该列表可以输入到生成列表的所有排列（也以递归方式实现）的函数。

总体来说，做法是：

1. 生成 1, 2, ... n 个数字的所有组合，其总和小于 goal
2. 生成这些组合的所有排列（这一步似乎没什么用，因为 sum 是可交换的，但我假设这是你的问题的定义）

请注意，这是 Subset Sum 的一个实例问题，这是一个困难的优化问题。下面的解决方案对于大型集合来说不能很好地扩展。

def unique_combination(in_list, goal, current_sum, current_path, accumulator):
    # Does a depth-first search of number *combinations* that sum exactly to `goal`
    # in_list is assumed sorted from smaller to largest

    for idx, current_element in enumerate(in_list):
        next_sum = current_sum + current_element
        if next_sum < goal:
            next_path = list(current_path)  # list is needed here to create a copy, as Python has a pass by reference semantics for lists
            next_path.append(current_element)
            unique_combination(in_list[idx+1:], goal, next_sum, next_path, accumulator)
        elif next_sum == goal:  # Arrived at a solution
            final_path = list(current_path)
            final_path.append(current_element)
            accumulator.append(final_path)
        else:   # Since in_list is ordered, all other numbers will fail after this
            break
    return accumulator

def permutations(elements):
    # Returns a list of all permutations of `elements`, calculated recursively
    if len(elements) == 1:
        return [elements]
    result = []
    for idx, el in enumerate(elements):
        other_elements = elements[:idx] + elements[idx+1:]
        all_perms = [[el] + sub_perms for sub_perms in permutations(other_elements)]
        result.extend(all_perms)
    return result

def myFunc(input_list, goal):
    # Sort the given elements
    input_list.sort()
    combinations = unique_combination(input_list, goal, 0, [], [])

    result = []
    for comb in combinations:
        result.extend(permutations(comb))
    return result

def print_results(results):
    for el in results:
        print(tuple(el)) # to get the parentheses

# Input:
a = [1,2,3,4,6,7,8]
k = 8
all_permutations = myFunc(a, k)
print_results(all_permutations)

# (1, 3, 4)
# (1, 4, 3)
# (3, 1, 4)
# (3, 4, 1)
# (4, 1, 3)
# (4, 3, 1)
# (1, 7)
# (7, 1)
# (2, 6)
# (6, 2)
# (8,)

Answer 2

使用 itertools 遍历候选者：

from itertools import permutations

A = [1,2,3,4,6,7]
K = 8 

for n in range(len(A) + 1):
    for perm in permutations(A, n):
        if sum(perm) == K:
            print(perm)

输出：

(1, 7)
(2, 6)
(6, 2)
(7, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)

Answer 3

使用排列

from itertools import permutations
k=8
data = [ 1, 2, 3, 4, 5, 6,7]
ans = []
for i in range(len(data)):
    ans.extend([values for values in permutations(data, i+1) if sum(values)==k])

print(ans)

输出：

$ python3 test.py
[(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]

一个线性解决方案：

k = 8

data = range(1, 8)

ans = [values for i in range(len(data)) for values in itertools.permutations(data, i+1) if sum(values) ==k]
print('permutations : ', ans)

输出：

permutations :  [(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]