[已解决]求解：数学问题

wmjrty

已知一数组N内有n个数[x1,x2,……xn]，给定一个数M，求数组N内有m种组合方式，使得组合之和等于M，m的值等于多少？且每种组合具体情况是什么？
举例：数组[1,2,3,4,5,6,7,8,9,10]，若M=10,则m=10，具体如下：
1.[10]
2.[1,9]
3.[2,8]
4.[3,7]
5.[4,6]
6.[1,2,7]
7.[1,3,6]
8.[1,4,5]
9.[2,3,5]
10.[1,2,3,4]

最佳答案

月排行榜 / 总排行榜

Stubborn

2022-1-2 17:00:36

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题主自行尝试修复，回帖就这样，拜拜
可以优化的地方，在最后双层嵌套循环的时候，res = two_sum(array[idx:index], target - sum(each))  ，这个index应该需要跟新，而不是固定的
比如当内层循环全排列的时候，each = (2,)的时候，idx=2, index=没有到理想的值，导致two_sum的搜索范围变大，这个值是可以通过search_index来获取的

避免重复计算

1.     # TODO 由3个组合，推导到最长组合
   
2.     # TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
   
3.     index = search_index(array, target)
   
4. 
   
5.     for width in range(1, max_length - 1):
   
6.         idx = width - 1
   
7.         for each in combinations(array[:index // 2], width):
   
8.             idx += 1
   
9.             res = two_sum(array[idx:index], target - sum(each))
   
10.             if not res:
    
11.                 break
    
12.             result += [list(each)+ e for e in res]
    
13.     return len(result), result

复制代码

1. from itertools import combinations
   
2. #
   
3. # ls = [1,2,3,4,5]
   
4. # print(list(c(ls, 2)))
   
5. from typing import List
   
6. 
   
7. 
   
8. def two_sum(array: List[int], target: int):
   
9.     """给定数组array，和目标值target,搜索所有的两个元素组合和值等于target"""
   
10.     result = []
    
11.     # TODO 如果当前数组0，1两个元素和大于target,或者0，-1两个元素和小于target
    
12.     if len(array) <= 2:
    
13.         return result
    
14.    
    
15.     if array[0] + array[1] > target or array[-2] + array[-1] < target:
    
16.         return result
    
17. 
    
18.     left, right = 0, len(array) - 1
    
19.     while left < right:
    
20.         value = array[left] + array[right]
    
21.         if value == target:
    
22.             result.append([array[left], array[right]])
    
23.             left += 1
    
24.         elif value > target:
    
25.             right -= 1
    
26.         else:
    
27.             left += 1
    
28.     return result
    
29. 
    
30. 
    
31. def search_index(array: List[int], target: int):
    
32.     """
    
33.     给定一个数组，搜索一个缩影，使得 array[index] < target - array[0] 并且 array[index+1] > target - array[0]
    
34.         如果没有搜索到，责返回一个None
    
35.     """
    
36.     left, right = 0, len(array)-1
    
37.     # TODO 如果当前数组的最后一个小于target,直接返回最大索引
    
38.     if array[right] < target:
    
39.         return len(array)
    
40.     # TODO 如果当前数组的第一个大于target,直接返回 None
    
41.     elif array[0] > target:
    
42.         return
    
43. 
    
44.     target = target - array[0]
    
45.     while left <= right:
    
46.         mid = (left + right) // 2
    
47.         if array[mid] <= target < array[mid + 1]:
    
48.             return mid
    
49.         elif array[mid] > target:
    
50.             right = mid - 1
    
51.         else:
    
52.             left = mid + 1
    
53. 
    
54. 
    
55. def get_all(array: List[int], target: int):
    
56.     """
    
57.     给定一个数组array， 一个定值target, 从array中选出n个元素，使得Sn = target, 求所有组合
    
58.         array是一个有序，有重复元素的数组
    
59.     """
    
60.     result = []
    
61.     # TODO 处理一个元素的组合
    
62.     num = array.count(target)
    
63.     if num:
    
64.         result += [target for _ in range(num)]
    
65. 
    
66.     # TODO max_length为最大组合长度，
    
67.     max_length = 0
    
68.     for index in range(len(array)):
    
69.         value = sum(array[:index])
    
70.         if value + array[index + 1] > target:
    
71.             max_length = index + 1
    
72.             break
    
73. 
    
74.     # TODO 如果没有符合的选项
    
75.     if max_length == 0:
    
76.         return 0, []
    
77.     # TODO 如果数组最大长度为1
    
78.     elif max_length == 1:
    
79.         return len(result), result
    
80.     # TODO 如果数组最大长度为2
    
81.     elif max_length == 2:
    
82.         result += two_sum(array, target)
    
83.         return len(result), result
    
84. 
    
85.     # TODO 由3个组合，推导到最长组合
    
86.     # TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
    
87.     index = search_index(array, target)
    
88. 
    
89.     for width in range(1, max_length-1):
    
90.         idx = width - 1
    
91.         for each in combinations(array[:index//2], width):
    
92.             idx += 1
    
93.             res = two_sum(array[idx:index], target - sum(each))
    
94.             # _index = search_index(array[: _index], target - sum_each)
    
95.             # res = two_sum(array[1:_index+1], target - sum_each)
    
96.             if res:
    
97.                 print(each, res)
    
98. 
    
99. nums = [1,2,3,4,5,6,7,8,9,10]
    
100. M = 20
     
101. print(nums[1:10])
     
102. get_all(nums, M)
     
103. 
     

复制代码

跳转到最佳答案楼层

Stubborn

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题主自行尝试修复，回帖就这样，拜拜
可以优化的地方，在最后双层嵌套循环的时候，res = two_sum(array[idx:index], target - sum(each))  ，这个index应该需要跟新，而不是固定的
比如当内层循环全排列的时候，each = (2,)的时候，idx=2, index=没有到理想的值，导致two_sum的搜索范围变大，这个值是可以通过search_index来获取的

避免重复计算

1.     # TODO 由3个组合，推导到最长组合
   
2.     # TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
   
3.     index = search_index(array, target)
   
4. 
   
5.     for width in range(1, max_length - 1):
   
6.         idx = width - 1
   
7.         for each in combinations(array[:index // 2], width):
   
8.             idx += 1
   
9.             res = two_sum(array[idx:index], target - sum(each))
   
10.             if not res:
    
11.                 break
    
12.             result += [list(each)+ e for e in res]
    
13.     return len(result), result

复制代码

1. from itertools import combinations
   
2. #
   
3. # ls = [1,2,3,4,5]
   
4. # print(list(c(ls, 2)))
   
5. from typing import List
   
6. 
   
7. 
   
8. def two_sum(array: List[int], target: int):
   
9.     """给定数组array，和目标值target,搜索所有的两个元素组合和值等于target"""
   
10.     result = []
    
11.     # TODO 如果当前数组0，1两个元素和大于target,或者0，-1两个元素和小于target
    
12.     if len(array) <= 2:
    
13.         return result
    
14.    
    
15.     if array[0] + array[1] > target or array[-2] + array[-1] < target:
    
16.         return result
    
17. 
    
18.     left, right = 0, len(array) - 1
    
19.     while left < right:
    
20.         value = array[left] + array[right]
    
21.         if value == target:
    
22.             result.append([array[left], array[right]])
    
23.             left += 1
    
24.         elif value > target:
    
25.             right -= 1
    
26.         else:
    
27.             left += 1
    
28.     return result
    
29. 
    
30. 
    
31. def search_index(array: List[int], target: int):
    
32.     """
    
33.     给定一个数组，搜索一个缩影，使得 array[index] < target - array[0] 并且 array[index+1] > target - array[0]
    
34.         如果没有搜索到，责返回一个None
    
35.     """
    
36.     left, right = 0, len(array)-1
    
37.     # TODO 如果当前数组的最后一个小于target,直接返回最大索引
    
38.     if array[right] < target:
    
39.         return len(array)
    
40.     # TODO 如果当前数组的第一个大于target,直接返回 None
    
41.     elif array[0] > target:
    
42.         return
    
43. 
    
44.     target = target - array[0]
    
45.     while left <= right:
    
46.         mid = (left + right) // 2
    
47.         if array[mid] <= target < array[mid + 1]:
    
48.             return mid
    
49.         elif array[mid] > target:
    
50.             right = mid - 1
    
51.         else:
    
52.             left = mid + 1
    
53. 
    
54. 
    
55. def get_all(array: List[int], target: int):
    
56.     """
    
57.     给定一个数组array， 一个定值target, 从array中选出n个元素，使得Sn = target, 求所有组合
    
58.         array是一个有序，有重复元素的数组
    
59.     """
    
60.     result = []
    
61.     # TODO 处理一个元素的组合
    
62.     num = array.count(target)
    
63.     if num:
    
64.         result += [target for _ in range(num)]
    
65. 
    
66.     # TODO max_length为最大组合长度，
    
67.     max_length = 0
    
68.     for index in range(len(array)):
    
69.         value = sum(array[:index])
    
70.         if value + array[index + 1] > target:
    
71.             max_length = index + 1
    
72.             break
    
73. 
    
74.     # TODO 如果没有符合的选项
    
75.     if max_length == 0:
    
76.         return 0, []
    
77.     # TODO 如果数组最大长度为1
    
78.     elif max_length == 1:
    
79.         return len(result), result
    
80.     # TODO 如果数组最大长度为2
    
81.     elif max_length == 2:
    
82.         result += two_sum(array, target)
    
83.         return len(result), result
    
84. 
    
85.     # TODO 由3个组合，推导到最长组合
    
86.     # TODO _index 是两个组合的最大索引值,由于是成对存在，所以 // 2
    
87.     index = search_index(array, target)
    
88. 
    
89.     for width in range(1, max_length-1):
    
90.         idx = width - 1
    
91.         for each in combinations(array[:index//2], width):
    
92.             idx += 1
    
93.             res = two_sum(array[idx:index], target - sum(each))
    
94.             # _index = search_index(array[: _index], target - sum_each)
    
95.             # res = two_sum(array[1:_index+1], target - sum_each)
    
96.             if res:
    
97.                 print(each, res)
    
98. 
    
99. nums = [1,2,3,4,5,6,7,8,9,10]
    
100. M = 20
     
101. print(nums[1:10])
     
102. get_all(nums, M)
     
103. 
     

复制代码

傻眼貓咪

小数目还行，大数目千万不要这样搞，除非你的电脑是超级电脑：

1. from itertools import permutations as p
   
2. 
   
3. arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   
4. ans = []
   
5. res = []
   
6. M = 10
   
7. N = len(arr)
   
8. 
   
9. for i in range(1, N+1):
   
10.     [ans.append(sorted(list(i))) for i in p(arr, i) if sum(list(i)) == M]
    
11. 
    
12. for i in ans:
    
13.     if i not in res:
    
14.         res.append(i)
    
15. 
    
16. for i in res:
    
17.     print(i)

复制代码

输出结果：

1. [10]
   
2. [1, 9]
   
3. [2, 8]
   
4. [3, 7]
   
5. [4, 6]
   
6. [1, 2, 7]
   
7. [1, 3, 6]
   
8. [1, 4, 5]
   
9. [2, 3, 5]
   
10. [1, 2, 3, 4]

复制代码

wmjrty

傻眼貓咪 发表于 2022-1-2 17:32
小数目还行，大数目千万不要这样搞，除非你的电脑是超级电脑：输出结果：

非常感谢！这个只是我举的简单例子。其实我想要的是针对大量数据的通用巧妙算法！

阿奇_o

1. >>> from itertools import combinations as c
   
2. >>> ls = [1,2,3,4,5,6,7,8,9,10]
   
3. >>> def func(ls, M=10):
   
4.         res = []
   
5.         for i in range(1, len(ls)+1):
   
6.                 for j in c(ls, i):
   
7.                         if sum(j) == M:
   
8.                                 res.append(j)
   
9.         return res, len(res)
   
10. 
    
11. >>> func(ls, M=10)
    
12. ([(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

数组是否有重复元素，是否是有序的数组，排序好的数据

wmjrty

Stubborn 发表于 2022-1-3 08:59
数组是否有重复元素，是否是有序的数组，排序好的数据

有重复元素，先有序吧。

Stubborn

wmjrty 发表于 2022-1-3 09:56
有重复元素，先有序吧。

数据量大，没有办法做到很大的优化。两个核心思想。
一。对于有序数组arry。搜索两个元素和值为M。由两侧同时向中心搜索，会更快（双指针）。
二。要N个里面选出n个元素，使得Sn = M 。肯定会用到全排，但是是有序的数组，所以n的最大值是可以被确定的。可以搜索一段连续的数据N[j:k]，有k - j = n和Sjk >= M。用来确保避免重复的排列搜索工具，具体代码，晚些时间在贴上

      

Ly_悠然天下

排序, 去重, 缺几找几(动态规划)
没了

wmjrty

Ly_悠然天下 发表于 2022-1-3 18:41
排序, 去重, 缺几找几(动态规划)
没了

应该不能绝对去重的。

Stubborn

wmjrty 发表于 2022-1-3 09:56
有重复元素，先有序吧。

#10楼跟新代码