从三元组合列表中提取覆盖全元素的无重叠唯一分组集合
三元组筛选实现方案
需求说明
给定如下三元组列表:
combinations=[[0, 1, 2],[0, 2, 3], [0, 2, 4],[5, 6, 8], [5, 6, 9],[6, 7, 10], [6, 8, 9],[3,4,11],[7,9,10],[1,4,7],[9,10,11]]
需要从中筛选符合以下要求的分组:
- 每个分组包含4个三元组
- 分组内所有元素无重复
- 恰好覆盖全部元素
[0,1,2,3,4,5,6,7,8,9,10,11]
实现代码
因为总共有11个三元组,选4个的组合数仅为330,直接暴力枚举所有可能的组合即可,实现简单且运行效率足够:
import itertools combinations = [[0, 1, 2],[0, 2, 3], [0, 2, 4],[5, 6, 8], [5, 6, 9],[6, 7, 10], [6, 8, 9],[3,4,11],[7,9,10],[1,4,7],[9,10,11]] valid_groups = [] # 枚举所有4个三元组的组合 for group in itertools.combinations(combinations, 4): # 展开所有元素到集合,12个不重复即符合要求 if len(set(num for triad in group for num in triad)) == 12: valid_groups.append(list(group)) # 格式化输出结果 for index, group in enumerate(valid_groups, 1): print(f"{index}) {group}")
输出示例
运行代码后会输出所有符合要求的分组,包含你给出的示例:
1) [[0, 1, 2], [5, 6, 8], [3, 4, 11], [7, 9, 10]] 2) [[0, 2, 3], [1, 4, 7], [5, 6, 8], [9, 10, 11]] ...
内容的提问来源于stack exchange,提问作者kev
相关产品推荐
相关产品推荐

