求解：数学问题
已知一数组N内有n个数，给定一个数M，求数组N内有m种组合方式，使得组合之和等于M，m的值等于多少？且每种组合具体情况是什么？举例：数组，若M=10,则m=10，具体如下：
1.
2.
3.
4.
5.
6.
7.
8.
9.
10. 本帖最后由 Stubborn 于 2022-1-4 13:07 编辑
Stubborn 发表于 2022-1-3 16:52
数据量大，没有办法做到很大的优化。两个核心思想。
一。对于有序数组arry。搜索两个元素和值为M。由两 ...
已知的BUG,
在92行处理idx索引有问题，导致计算元素重复。待修，其他bug，待数据集测试。批注打印的结果是三个组合以上数组比如1，2，7
已修复BUG。90行代码。idx = 0 修改为 idx = width - 1
已知的BUG,
对于重复数据，在搜索两个数的的组合会有忽略的情况，发生在two_sum里面。
对于最后的结果集和bug题主自行尝试修复，回帖就这样，拜拜{:10_260:}
可以优化的地方，在最后双层嵌套循环的时候，res = two_sum(array, target - sum(each))，这个index应该需要跟新，而不是固定的
比如当内层循环全排列的时候，each = (2,)的时候，idx=2, index=没有到理想的值，导致two_sum的搜索范围变大，这个值是可以通过search_index来获取的
避免重复计算
# TODO 由3个组合，推导到最长组合
# TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
index = search_index(array, target)
for width in range(1, max_length - 1):
idx = width - 1
for each in combinations(array[:index // 2], width):
idx += 1
res = two_sum(array, target - sum(each))
if not res:
break
result +=
return len(result), result
from itertools import combinations
#
# ls =
# print(list(c(ls, 2)))
from typing import List
def two_sum(array: List, target: int):
"""给定数组array，和目标值target,搜索所有的两个元素组合和值等于target"""
result = []
# TODO 如果当前数组0，1两个元素和大于target,或者0，-1两个元素和小于target
if len(array) <= 2:
return result
if array + array > target or array[-2] + array[-1] < target:
return result
left, right = 0, len(array) - 1
while left < right:
value = array + array
if value == target:
result.append(, array])
left += 1
elif value > target:
right -= 1
else:
left += 1
return result
def search_index(array: List, target: int):
"""
给定一个数组，搜索一个缩影，使得 array < target - array 并且 array > target - array
如果没有搜索到，责返回一个None
"""
left, right = 0, len(array)-1
# TODO 如果当前数组的最后一个小于target,直接返回最大索引
if array < target:
return len(array)
# TODO 如果当前数组的第一个大于target,直接返回 None
elif array > target:
return
target = target - array
while left <= right:
mid = (left + right) // 2
if array <= target < array:
return mid
elif array > target:
right = mid - 1
else:
left = mid + 1
def get_all(array: List, target: int):
"""
给定一个数组array， 一个定值target, 从array中选出n个元素，使得Sn = target, 求所有组合
array是一个有序，有重复元素的数组
"""
result = []
# TODO 处理一个元素的组合
num = array.count(target)
if num:
result +=
# TODO max_length为最大组合长度，
max_length = 0
for index in range(len(array)):
value = sum(array[:index])
if value + array > target:
max_length = index + 1
break
# TODO 如果没有符合的选项
if max_length == 0:
return 0, []
# TODO 如果数组最大长度为1
elif max_length == 1:
return len(result), result
# TODO 如果数组最大长度为2
elif max_length == 2:
result += two_sum(array, target)
return len(result), result
# TODO 由3个组合，推导到最长组合
# TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
index = search_index(array, target)
for width in range(1, max_length-1):
idx = width - 1
for each in combinations(array[:index//2], width):
idx += 1
res = two_sum(array, target - sum(each))
# _index = search_index(array[: _index], target - sum_each)
# res = two_sum(array, target - sum_each)
if res:
print(each, res)
nums =
M = 20
print(nums)
get_all(nums, M)
小数目还行，大数目千万不要这样搞，除非你的电脑是超级电脑：from itertools import permutations as p
arr =
ans = []
res = []
M = 10
N = len(arr)
for i in range(1, N+1):
for i in ans:
if i not in res:
res.append(i)
for i in res:
print(i)输出结果：
傻眼貓咪 发表于 2022-1-2 17:32
小数目还行，大数目千万不要这样搞，除非你的电脑是超级电脑：输出结果：
非常感谢！这个只是我举的简单例子。其实我想要的是针对大量数据的通用巧妙算法！ >>> from itertools import combinations as c
>>> ls =
>>> def func(ls, M=10):
res = []
for i in range(1, len(ls)+1):
for j in c(ls, i):
if sum(j) == M:
res.append(j)
return res, len(res)
>>> func(ls, M=10)
([(10,), (1, 9), (2, 8), (3, 7), (4, 6), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5), (1, 2, 3, 4)], 10) 本帖最后由 Stubborn 于 2022-1-3 09:39 编辑
数组是否有重复元素，是否是有序的数组，排序好的数据 Stubborn 发表于 2022-1-3 08:59
数组是否有重复元素，是否是有序的数组，排序好的数据
有重复元素，先有序吧。 wmjrty 发表于 2022-1-3 09:56
有重复元素，先有序吧。
数据量大，没有办法做到很大的优化。两个核心思想。
一。对于有序数组arry。搜索两个元素和值为M。由两侧同时向中心搜索，会更快（双指针）。
二。要N个里面选出n个元素，使得Sn = M 。肯定会用到全排，但是是有序的数组，所以n的最大值是可以被确定的。可以搜索一段连续的数据N，有k - j = n和Sjk >= M。用来确保避免重复的排列搜索工具，具体代码，晚些时间在贴上
排序, 去重, 缺几找几(动态规划)
没了 Ly_悠然天下 发表于 2022-1-3 18:41
排序, 去重, 缺几找几(动态规划)
没了
应该不能绝对去重的。 wmjrty 发表于 2022-1-3 09:56
有重复元素，先有序吧。
#10楼跟新代码
页:
[1]