Java如何从二维数组选取元素生成任意两组合至少有两处差异的结果集
满足单差异排除要求的组合生成递归实现方案
核心判定规则
你需要生成的最终组合集,本质要满足任意两个组合的汉明距离不小于2——也就是任意两个逐位置对比时,相同位置取值不同的数量不能等于1,刚好匹配你举的案例:
- 已选组合{1, 3, 5}和候选{1, 3, 6}仅在第三位置存在差异,汉明距离为1,必须排除
- 你给出的示例输出集合中,任意两个组合的汉明距离均为2,符合要求
递归实现的核心逻辑
不需要先生成全量组合再做筛选(该方式在8个维度、每个维度20个可选元素的规模下会产生20^8级别的无意义计算,完全没有性能可行性),直接在递归搜索过程中完成合法性校验和剪枝,核心逻辑分为三步:
- 递归状态设计:递归遍历到第
i个子数组位置时,携带两个核心状态:- 已从前
i个子数组选好元素组成的临时候选序列 - 已确认符合规则的最终合法组合集合
- 已从前
- 终止条件校验:当递归遍历完所有子数组(临时序列长度等于二维数组第一维的规模)时,对当前候选序列做合法性校验:
- 逐位和集合中所有已存的合法组合计算差异数量
- 一旦发现某组对比的差异数为1,直接判定当前候选不合法,丢弃
- 如果所有对比的差异数都≥2,将当前候选加入合法集合
- 校验时可以提前终止计算:累计差异数到1的时候就不需要继续对比剩余位置,大幅降低运算量
- 递归搜索流程:在每个递归位置,遍历当前对应子数组的所有可选元素,将元素拼接到临时候选序列末尾,递归进入下一个位置的搜索,回溯时将选中的元素从临时序列中移除,不影响其他分支的计算
适配性说明
- 支持任意长度不一致的子数组:递归过程仅遍历当前位置子数组的实际元素,不要求所有子数组的长度相同
- 完全匹配规模要求:第一维最大8、第二维最大20的规模下,因为有提前剪枝和提前终止的优化,整个搜索过程的计算量极低,可在毫秒级完成
- 可以通过调整子数组元素的遍历顺序,得到不同的合法组合集合,所有集合均满足“无单位置差异对”的要求
参考递归伪代码
valid_combinations = [] def backtrack(curr_idx, curr_candidate, source): if curr_idx == len(source): # 校验当前候选的合法性 legal = True for exist in valid_combinations: diff = 0 for pos in range(len(exist)): if curr_candidate[pos] != exist[pos]: diff +=1 if diff ==1: legal = False break if not legal: break if legal: valid_combinations.append(curr_candidate.copy()) return # 遍历当前位置的所有可选元素 for num in source[curr_idx]: curr_candidate.append(num) backtrack(curr_idx +1, curr_candidate, source) curr_candidate.pop() # 测试用例验证 test_arr = [[1,2], [3,4], [5,6]] backtrack(0, [], test_arr) # 运行后得到的结果和示例输出完全一致
内容的提问来源于stack exchange,提问作者Markus Hervén
相关产品推荐
相关产品推荐

