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

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来获取的

避免重复计算

    # 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[idx:index], target - sum(each))
            if not res:
                break
            result += [list(each)+ e for e in res]
    return len(result), result

from itertools import combinations
#
# ls = [1,2,3,4,5]
# print(list(c(ls, 2)))
from typing import List


def two_sum(array: List[int], target: int):
    """给定数组array，和目标值target,搜索所有的两个元素组合和值等于target"""
    result = []
    # TODO 如果当前数组0，1两个元素和大于target,或者0，-1两个元素和小于target
    if len(array) <= 2:
        return result
    
    if array[0] + array[1] > target or array[-2] + array[-1] < target:
        return result

    left, right = 0, len(array) - 1
    while left < right:
        value = array[left] + array[right]
        if value == target:
            result.append([array[left], array[right]])
            left += 1
        elif value > target:
            right -= 1
        else:
            left += 1
    return result


def search_index(array: List[int], target: int):
    """
    给定一个数组，搜索一个缩影，使得 array[index] < target - array[0] 并且 array[index+1] > target - array[0]
        如果没有搜索到，责返回一个None
    """
    left, right = 0, len(array)-1
    # TODO 如果当前数组的最后一个小于target,直接返回最大索引
    if array[right] < target:
        return len(array)
    # TODO 如果当前数组的第一个大于target,直接返回 None
    elif array[0] > target:
        return

    target = target - array[0]
    while left <= right:
        mid = (left + right) // 2
        if array[mid] <= target < array[mid + 1]:
            return mid
        elif array[mid] > target:
            right = mid - 1
        else:
            left = mid + 1


def get_all(array: List[int], target: int):
    """
    给定一个数组array， 一个定值target, 从array中选出n个元素，使得Sn = target, 求所有组合
        array是一个有序，有重复元素的数组
    """
    result = []
    # TODO 处理一个元素的组合
    num = array.count(target)
    if num:
        result += [target for _ in range(num)]

    # TODO max_length为最大组合长度，
    max_length = 0
    for index in range(len(array)):
        value = sum(array[:index])
        if value + array[index + 1] > 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[idx:index], target - sum(each))
            # _index = search_index(array[: _index], target - sum_each)
            # res = two_sum(array[1:_index+1], target - sum_each)
            if res:
                print(each, res)

nums = [1,2,3,4,5,6,7,8,9,10]
M = 20
print(nums[1:10])
get_all(nums, M)

跳转到最佳答案楼层

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来获取的

避免重复计算

    # 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[idx:index], target - sum(each))
            if not res:
                break
            result += [list(each)+ e for e in res]
    return len(result), result

from itertools import combinations
#
# ls = [1,2,3,4,5]
# print(list(c(ls, 2)))
from typing import List


def two_sum(array: List[int], target: int):
    """给定数组array，和目标值target,搜索所有的两个元素组合和值等于target"""
    result = []
    # TODO 如果当前数组0，1两个元素和大于target,或者0，-1两个元素和小于target
    if len(array) <= 2:
        return result
    
    if array[0] + array[1] > target or array[-2] + array[-1] < target:
        return result

    left, right = 0, len(array) - 1
    while left < right:
        value = array[left] + array[right]
        if value == target:
            result.append([array[left], array[right]])
            left += 1
        elif value > target:
            right -= 1
        else:
            left += 1
    return result


def search_index(array: List[int], target: int):
    """
    给定一个数组，搜索一个缩影，使得 array[index] < target - array[0] 并且 array[index+1] > target - array[0]
        如果没有搜索到，责返回一个None
    """
    left, right = 0, len(array)-1
    # TODO 如果当前数组的最后一个小于target,直接返回最大索引
    if array[right] < target:
        return len(array)
    # TODO 如果当前数组的第一个大于target,直接返回 None
    elif array[0] > target:
        return

    target = target - array[0]
    while left <= right:
        mid = (left + right) // 2
        if array[mid] <= target < array[mid + 1]:
            return mid
        elif array[mid] > target:
            right = mid - 1
        else:
            left = mid + 1


def get_all(array: List[int], target: int):
    """
    给定一个数组array， 一个定值target, 从array中选出n个元素，使得Sn = target, 求所有组合
        array是一个有序，有重复元素的数组
    """
    result = []
    # TODO 处理一个元素的组合
    num = array.count(target)
    if num:
        result += [target for _ in range(num)]

    # TODO max_length为最大组合长度，
    max_length = 0
    for index in range(len(array)):
        value = sum(array[:index])
        if value + array[index + 1] > 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[idx:index], target - sum(each))
            # _index = search_index(array[: _index], target - sum_each)
            # res = two_sum(array[1:_index+1], target - sum_each)
            if res:
                print(each, res)

nums = [1,2,3,4,5,6,7,8,9,10]
M = 20
print(nums[1:10])
get_all(nums, M)

傻眼貓咪

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

from itertools import permutations as p

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
ans = []
res = []
M = 10
N = len(arr)

for i in range(1, N+1):
    [ans.append(sorted(list(i))) for i in p(arr, i) if sum(list(i)) == M]

for i in ans:
    if i not in res:
        res.append(i)

for i in res:
    print(i)

输出结果：

[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]

wmjrty

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

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

阿奇_o

>>> from itertools import combinations as c
>>> ls = [1,2,3,4,5,6,7,8,9,10]
>>> 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

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

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楼跟新代码