如何从筛选后的二元组合列表还原生成它的原元素子集？

核心思路 #

给定筛选后的二元组合列表（满足两元素和>14），我们需要找到一个原元素子集T，使得从T生成的所有无重复二元组合中，满足和>14的组合恰好等于输入的列表。如果不存在这样的T，则判定为无法对应。

实现步骤如下：

1. 从输入列表中提取所有出现过的元素，组成候选元素集合（T必须包含这些元素，否则无法生成对应组合）。
2. 遍历候选元素的所有非空子集（大小≥2），对每个子集生成所有二元组合并筛选出符合和>14的结果。
3. 将筛选结果与输入列表排序后对比，完全匹配的子集即为有效解。
4. 去重后返回所有有效解，若无解则返回提示。

Python代码实现 #

import itertools

def restore_original_subset(result_list):
    # 提取所有出现过的元素并去重
    candidates = set()
    for pair in result_list:
        candidates.update(pair)
    candidates = sorted(candidates)
    
    solutions = []
    n = len(candidates)
    
    # 遍历所有可能的子集（大小从2开始，因为二元组合至少需要2个元素）
    for subset_size in range(2, n + 1):
        for subset_tuple in itertools.combinations(candidates, subset_size):
            # 生成当前子集的所有二元组合
            generated_pairs = itertools.combinations(subset_tuple, 2)
            # 筛选出和大于14的组合
            filtered_pairs = [pair for pair in generated_pairs if pair[0] + pair[1] > 14]
            
            # 统一排序后对比（消除顺序影响）
            sorted_input = sorted(tuple(sorted(p)) for p in result_list)
            sorted_filtered = sorted(tuple(sorted(p)) for p in filtered_pairs)
            
            if sorted_input == sorted_filtered:
                solutions.append(set(subset_tuple))
    
    # 去重并整理结果
    unique_solutions = []
    seen = set()
    for sol in solutions:
        frozen_sol = frozenset(sol)
        if frozen_sol not in seen:
            seen.add(frozen_sol)
            unique_solutions.append(sorted(sol))
    
    return unique_solutions if unique_solutions else "无法对应任何子集"

# 测试示例
if __name__ == "__main__":
    # 示例1：对应子集{6,9,10}
    test1 = [(6.0,9.0), (6.0,10.0), (9.0,10.0)]
    print("测试1结果:", restore_original_subset(test1))  # 输出 [[6.0, 9.0, 10.0]]
    
    # 示例2：单个组合(5,10)对应子集{5,10}
    test2 = [(5.0,10.0)]
    print("测试2结果:", restore_original_subset(test2))  # 输出 [[5.0, 10.0]]
    
    # 示例3：无法对应的组合列表
    test3 = [(5.0,10.0), (6.0,9.0)]
    print("测试3结果:", restore_original_subset(test3))  # 输出 无法对应任何子集

关键细节说明 #

• 排序对比：对组合和列表排序是为了消除元组顺序（如(6,9)和(9,6)视为同一组合）以及列表内的顺序差异，确保对比准确。
• 子集遍历范围：只考虑大小≥2的子集，因为单个元素无法生成二元组合。
• 去重处理：用frozenset记录已发现的解，避免因子集生成顺序不同导致的重复结果。

特殊情况解释 #

• 对于单个组合[(5,10)]，有效解是{5,10}——该子集仅有的二元组合满足和>14，与输入完全匹配。
• 对于混合组合[(5,10), (6,9)]，不存在有效子集：任何包含所有四个元素的子集会额外生成(6,10)、(9,10)等符合条件的组合，而仅包含部分元素的子集无法覆盖所有输入组合，因此判定为无法对应。

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