查找 Sum 等于给定数字的列表的不同部分
Find Distinct parts of List that Sum are equal to the given Number
我想从没有重复数字的输入列表中找到总和等于 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)
这个函数Return:
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)
那么，我应该如何处理代码才能实现我的结果...
您的原始函数正在正确生成可能的组合。唯一的问题是您正在打印它，而不是将其保存在列表中以备后用。
我对其进行了修改，以便将结果保存到一个列表中，该列表可以输入到一个函数中，该函数生成一个列表的所有排列（也以递归方式实现）。
总的来说，方法是：
- 生成总和小于
goal 的 1、2、... n 个数字的所有组合
- 生成这些组合的所有排列（这一步似乎没用，因为总和是可交换的，但我假设这就是你问题的定义）
请注意，这是 Subset Sum Problem 的一个实例，这是一个困难的优化问题。下面的解决方案不适用于大型集合。
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,)
使用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)
使用排列
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)]
我想从没有重复数字的输入列表中找到总和等于 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)
这个函数Return:
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)
那么，我应该如何处理代码才能实现我的结果...
您的原始函数正在正确生成可能的组合。唯一的问题是您正在打印它，而不是将其保存在列表中以备后用。
我对其进行了修改，以便将结果保存到一个列表中，该列表可以输入到一个函数中，该函数生成一个列表的所有排列（也以递归方式实现）。
总的来说，方法是：
- 生成总和小于
goal 的 1、2、... n 个数字的所有组合
- 生成这些组合的所有排列（这一步似乎没用，因为总和是可交换的，但我假设这就是你问题的定义）
请注意，这是 Subset Sum Problem 的一个实例，这是一个困难的优化问题。下面的解决方案不适用于大型集合。
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,)
使用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)
使用排列
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)]