寻找无重复和整数集：Python算法优化求助

问题描述 #

需要生成包含P个不同整数的集合，要求从中选取G个可重复元素的多重集组合（不考虑元素顺序）的和唯一（无碰撞）。例如P=3、G=3时，集合(10,1,0)符合要求，但(2,1,0)不符合（1+1+1=2+1+0）。现有递归回溯算法在P=7、G=3且maxPts达到70左右时，每次迭代耗时数分钟，需优化性能。

现有代码的核心瓶颈 #

1. 碰撞检测逻辑错误且低效：原test_no_colls枚举所有有序G元组，将同一多重集的不同排列误判为碰撞，同时O(P^G)的时间复杂度随P、G增大指数级爆炸。
2. 递归搜索冗余：未利用集合的数学特性提前剪枝，导致大量无效候选集被检测。
3. 数值计算开销大：过度依赖numpy数组处理小数据，增加了不必要的初始化和操作开销。

针对性优化方案 #

1. 修正并优化碰撞检测 #

方法：枚举多重集组合

直接枚举所有合法的多重集组合（避免重复排列），计算和并检查唯一性，时间复杂度为O(C(P+G-1, G))，远低于O(P^G)：

def test_no_colls_multiset(nums, G):
    sums = set()
    nums_sorted = sorted(nums)

    def backtrack(start, remaining, current_sum):
        if remaining == 0:
            if current_sum in sums:
                return False
            sums.add(current_sum)
            return True
        for i in range(start, len(nums_sorted)):
            num = nums_sorted[i]
            if not backtrack(i, remaining - 1, current_sum + num):
                return False
        return True

    return backtrack(0, G, 0)

进阶优化：缓存中间结果

用lru_cache缓存子集的检测结果，避免重复计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def test_no_colls_cached(nums_tuple, G):
    sums = set()
    nums_sorted = sorted(nums_tuple)

    def backtrack(start, remaining, current_sum):
        if remaining == 0:
            if current_sum in sums:
                return False
            sums.add(current_sum)
            return True
        for i in range(start, len(nums_sorted)):
            num = nums_sorted[i]
            if not backtrack(i, remaining - 1, current_sum + num):
                return False
        return True

    return backtrack(0, G, 0)

# 使用时将列表转为元组传入
test_no_colls_cached(tuple(nums[:index+1]), G)

2. 优化递归搜索逻辑 #

• 提前终止递归：一旦找到符合条件的集合，立即返回，停止后续无效搜索：

def rec_test_list(leng, index, nums, G, func, foundOne):
    if foundOne:
        return True
    if index == leng - 1:
        foundNew = func(nums)
        return foundNew
    nextMax = nums[index-1]
    for nextNum in range(nextMax)[::-1]:
        nums[index] = nextNum
        if test_no_colls_cached(tuple(nums[:index+1]), G):
            foundOne = rec_test_list(leng, index+1, nums, G, func, foundOne)
            if foundOne:
                return True
    return foundOne

• 替换numpy为Python列表：小数据场景下，Python列表的初始化和操作开销远低于numpy数组：

def test_all_lists(leng, first, G, func):
    nums = [0]*leng
    nums[0] = first
    return rec_test_list(leng, 1, nums, G, func, False)

3. 利用数学特性剪枝 #

构造G-安全递增序列：要求每个新元素大于G倍的前一个元素，这样包含新元素的组合和必然大于不包含它的最大组合和（G*前一个元素），天然避免碰撞。在递归生成候选集时加入该条件，可大幅减少搜索分支：

def is_g_safe_increasing(nums, G):
    if len(nums) <= 1:
        return True
    for i in range(1, len(nums)):
        if nums[i] >= nums[i-1] or nums[i-1] <= G * nums[i]:
            return False
    return True

# 在递归中加入剪枝
if is_g_safe_increasing(nums[:index+1], G) and test_no_colls_cached(tuple(nums[:index+1]), G):
    # 继续递归

更优思路：构造性算法 #

若不追求最小maxPts，可直接构造符合条件的集合，完全避免搜索开销：

1. 进制构造法 #

选择集合元素为0, 1, K, K², ..., K^{P-2}，其中K > G。每个元素是K的幂，任意G个元素的和对应唯一的G进制数，因此和必然唯一。例如G=3、P=3时，K=4，集合为{0,1,4}，所有3元素组合的和均不重复。

2. 贪心构造最小序列 #

从小到大选择元素，每次取满足条件的最小整数：

• 初始集合：{0}
• 后续元素：取大于G倍前一个元素的最小整数（确保新元素的组合和不与旧组合和碰撞）
  例如G=3时，序列为0,1,4,13,40,...，每个元素满足s_i = 3*s_{i-1}+1，构造简单且保证无碰撞。

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