如何获取列表中元素使用次数不超出现有次数的唯一目标和组合

问题分析 #

你当前的代码存在两个核心问题：

• 重复组合：itertools.combinations基于原列表的位置生成子集，原列表中重复的元素（如5.4出现3次）会导致不同位置的相同元素生成内容重复的组合（比如(5.4,5.4,8.1)和(5.4,8.1,5.4)）。
• 浮点数精度风险：直接用==比较浮点数的和与目标值，可能因为浮点数运算的精度误差导致漏判或误判。
• 额外的错误组合：比如(5.4,9.0,4.5)的和确实是18.9，若你认为它不符合预期，需要确认是否是对需求的理解偏差——该组合的元素使用次数均未超过原列表的出现次数（5.4用1次，9.0和4.5各1次，都在原列表的频次范围内）。

解决方案 #

我们可以通过统计元素频次+回溯生成合法组合+浮点数近似比较的方式解决问题，同时确保组合不重复：

代码实现 #

from collections import Counter

def find_target_combinations(lst, target):
    # 统计元素及其出现次数，同时排序元素避免重复组合
    count = Counter(lst)
    elements = sorted(count.keys())
    result = []
    
    def backtrack(index, current_combination, current_sum):
        # 用近似比较处理浮点数精度问题
        if abs(current_sum - target) < 1e-9:
            result.append(tuple(current_combination))
            return
        if current_sum > target + 1e-9 or index >= len(elements):
            return
        
        elem = elements[index]
        # 尝试使用0到该元素最大可用次数
        max_usage = count[elem]
        for usage in range(0, max_usage + 1):
            # 添加usage个当前元素到组合中
            for _ in range(usage):
                current_combination.append(elem)
                current_sum += elem
            # 递归处理下一个元素
            backtrack(index + 1, current_combination, current_sum)
            # 回溯：移除添加的元素
            for _ in range(usage):
                current_combination.pop()
                current_sum -= elem
    
    backtrack(0, [], 0.0)
    # 过滤掉空组合
    return [comb for comb in result if comb]

# 测试代码
magicnumber = 18.9
lst = [2.7, 9.9, 5.4, 9.0, 5.4, 8.1, 6.3, 4.5, 5.4]
combinations = find_target_combinations(lst, magicnumber)

for comb in combinations:
    print(comb)

代码说明 #

1. 统计频次：用Counter统计每个元素在原列表中的出现次数，确保后续组合中元素的使用次数不超过这个上限。
2. 排序元素：对元素进行排序，确保生成的组合是有序的，从根源避免因元素顺序不同导致的重复组合。
3. 回溯法：递归遍历每个元素，尝试使用0到最大可用次数的该元素，逐步构建组合并计算总和。
4. 浮点数处理：用abs(current_sum - target) < 1e-9替代直接的==比较，避免浮点数精度误差带来的问题。

运行结果 #

运行上述代码后，你会得到以下结果：

(2.7, 4.5, 5.4, 6.3)
(4.5, 5.4, 9.0)
(5.4, 5.4, 8.1)
(9.0, 9.9)

如果你确实需要排除(4.5,5.4,9.0)这个组合，需要明确额外的筛选条件（比如组合长度限制等），否则该组合是符合原始需求的。

另一种简化实现（基于itertools） #

如果你倾向于用itertools，可以先对原列表排序，然后生成组合后去重（通过排序元组的方式），同时处理浮点数精度：

import itertools

magicnumber = 18.9
lst = [2.7, 9.9, 5.4, 9.0, 5.4, 8.1, 6.3, 4.5, 5.4]
lst_sorted = sorted(lst)
seen = set()

for L in range(1, len(lst_sorted)+1):
    for subset in itertools.combinations(lst_sorted, L):
        # 处理浮点数精度
        if abs(sum(subset) - magicnumber) < 1e-9:
            # 排序子集后转成元组，用于去重
            sorted_subset = tuple(sorted(subset))
            if sorted_subset not in seen:
                seen.add(sorted_subset)
                print(sorted_subset)

这个方法的原理是：先对原列表排序，生成的组合本身是有序的，再对每个子集排序后存入集合去重，确保相同元素的不同排列不会被重复输出。

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