我想從沒有重復數字的輸入串列中找到總和等于 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)
那么，我應該如何處理代碼來實作我的結果......
uj5u.com熱心網友回復：
您的原始功能正在正確生成可能的組合。唯一的問題是您正在列印它，而不是將其保存在串列中以供以后使用。
我對其進行了修改，以便將結果保存到串列中，該串列可以輸入到生成串列的所有排列（也以遞回方式實作）的函式中。
總的來說，方法是：
- 生成總和小于的 1、2、...n 個數字的所有組合
goal - 生成這些組合的所有排列（這一步似乎沒用，因為 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,)
uj5u.com熱心網友回復：
用于通過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)
uj5u.com熱心網友回復：
使用排列
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)]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/434912.html
上一篇：數的數積