基于Numpy的目标和组合查找算法优化问询

问题描述 #

我有一个浮点型NumPy数组，需要找出所有元素相加等于指定目标和的组合。当前实现效率极低，仅处理50个元素就耗时极久。

约束条件 #

• 数组中可能存在重复值
• 数组大小范围：0 < array.size < 1000000
• 元素取值范围：0 <= element <= 999,999,999,999.99

现有实现（已翻译注释） #

import numpy as np
from typing import List, Tuple, Set
from collections import defaultdict

def generate_random_array(size=1000, min_val=0, max_val=100, seed=42):
    np.random.seed(seed)
    arr = np.random.uniform(min_val, max_val, size)
    return np.round(arr, 2)

def find_target_sum_combinations(arr: np.ndarray, target: float, min_elements: int = 2, epsilon: float = 1e-10) -> List[Tuple[float, ...]]:

    arr = np.asarray(arr, dtype=np.float64)
    n = len(arr)
    
    # 哈希表存储组合：键为和的标识，值为索引组合集合
    dp = defaultdict(set)
    
    # 将浮点型和转换为整数键，避免浮点精度问题
    def get_sum_key(value: float) -> int:
        return int(round(value / epsilon))
    
    # 初始化：添加所有单个元素的索引
    for i, num in enumerate(arr):
        dp[get_sum_key(num)].add((i,))
    
    result = []

    
    # 将每个新元素与已有的所有组合进行合并
    for i in range(n):
        curr_num = arr[i]
        # 复制当前的和集合，避免迭代时修改原数据
        current_sums = list(dp.items())
        
        for sum_key, combinations in current_sums:
            new_sum = sum_key * epsilon + curr_num
            new_sum_key = get_sum_key(new_sum)
            
            # 生成新的组合
            for comb in combinations:
                # 确保不重复使用同一元素（通过索引大小判断，避免重复组合）
                if i > max(comb):
                    new_comb = comb + (i,)
                    dp[new_sum_key].add(new_comb)
                    
                    # 检查是否满足目标和与最小元素数量要求
                    if (abs(new_sum - target) < epsilon and 
                        len(new_comb) >= min_elements):
                        result.append(tuple(float(arr[idx]) for idx in new_comb))
    
    return sorted(result, key=len)


arr=generate_random_array(size=20, min_val=1000, max_val=100000, seed=42)
target_sum=arr[1]+arr[2]+arr[4]+arr[5]

combinations = find_target_sum_combinations(arr, target_sum)
print(f"\nCombinations that sum to {target_sum}:")
for comb in combinations:
    print(f"{comb} = {sum(comb)}")

原代码效率低下的原因 #

1. 组合爆炸：每次迭代都要遍历所有已生成的组合，随着元素数量增加，组合数呈指数级增长（n=50时组合数可达2^50量级，完全无法处理）。
2. 重复计算：未对数组中的重复值做优化，导致大量重复的组合计算。
3. 浮点精度处理冗余：虽然用整数键规避精度问题，但每次计算新和都要做浮点转换，额外增加开销。

优化方案：分治法（Meet-in-the-Middle） #

分治法将数组拆分为两半，分别计算每一半的所有可能组合的和，再在两个半区的和中查找互补对（即和为目标值的组合）。时间复杂度从O(2^{n)降至O(n*2}(n/2))，能处理n=50左右的数组。

同时，将所有浮点值转为整数（因元素最多保留两位小数，乘以100即可），彻底避免浮点精度误差。

优化后的代码 #

import numpy as np
from typing import List, Tuple, Dict
from collections import defaultdict

def generate_random_array(size=1000, min_val=0, max_val=100, seed=42):
    np.random.seed(seed)
    arr = np.random.uniform(min_val, max_val, size)
    return np.round(arr, 2)

def find_target_sum_combinations(arr: np.ndarray, target: float, min_elements: int = 2) -> List[Tuple[float, ...]]:
    # 转换为整数处理，规避浮点精度问题
    target_int = int(round(target * 100))
    arr_int = np.round(arr * 100).astype(np.int64)
    n = len(arr_int)
    
    # 拆分数组为左右两半
    mid = n // 2
    left_arr = arr_int[:mid]
    right_arr = arr_int[mid:]
    
    # 预计算左半区所有组合的和与对应索引
    left_sum_map: Dict[int, List[Tuple[int, ...]]] = defaultdict(list)
    for mask in range(1, 1 << len(left_arr)):
        indices = tuple(i for i in range(len(left_arr)) if (mask >> i) & 1)
        total = sum(left_arr[i] for i in indices)
        left_sum_map[total].append(indices)
    
    result = []
    # 遍历右半区所有组合，查找左半区的互补和
    for mask in range(1, 1 << len(right_arr)):
        right_indices = tuple(mid + i for i in range(len(right_arr)) if (mask >> i) & 1)
        right_total = sum(right_arr[i] for i in range(len(right_arr)) if (mask >> i) & 1)
        complement = target_int - right_total
        
        if complement in left_sum_map:
            for left_indices in left_sum_map[complement]:
                full_indices = left_indices + right_indices
                if len(full_indices) >= min_elements:
                    # 转换回原始浮点值
                    combination = tuple(arr[idx] for idx in full_indices)
                    result.append(combination)
    
    # 去重（处理数组重复值导致的重复组合）
    result = list(set(result))
    # 按组合长度排序
    result.sort(key=len)
    return result


# 测试示例
arr = generate_random_array(size=20, min_val=1000, max_val=100000, seed=42)
target_sum = arr[1] + arr[2] + arr[4] + arr[5]

combinations = find_target_sum_combinations(arr, target_sum)
print(f"\n和为 {target_sum:.2f} 的组合：")
for comb in combinations:
    print(f"{comb} = {sum(comb):.2f}")

注意事项 #

如果数组大小超过40左右，即使分治法也会因组合数过多无法处理（n=50时2^{25约为3300万，n=60时2}30超过10亿，计算量陡增）。若数组接近1e6量级，枚举所有组合完全不现实，此时需要重新明确需求：是否仅需特定长度的组合？或是否可接受近似解？

内容的提问来源于stack exchange，提问作者Ramon Martin