You need to enable JavaScript to run this app. Java如何从二维数组选取元素生成任意两组合至少有两处差异的结果集
优惠活动
大模型
产品
解决方案
定价
更多

Java如何从二维数组选取元素生成任意两组合至少有两处差异的结果集

满足单差异排除要求的组合生成递归实现方案

核心判定规则

你需要生成的最终组合集,本质要满足任意两个组合的汉明距离不小于2——也就是任意两个逐位置对比时,相同位置取值不同的数量不能等于1,刚好匹配你举的案例:

  • 已选组合{1, 3, 5}和候选{1, 3, 6}仅在第三位置存在差异,汉明距离为1,必须排除
  • 你给出的示例输出集合中,任意两个组合的汉明距离均为2,符合要求

递归实现的核心逻辑

不需要先生成全量组合再做筛选(该方式在8个维度、每个维度20个可选元素的规模下会产生20^8级别的无意义计算,完全没有性能可行性),直接在递归搜索过程中完成合法性校验和剪枝,核心逻辑分为三步:

  1. 递归状态设计:递归遍历到第i个子数组位置时,携带两个核心状态:
    • 已从前i个子数组选好元素组成的临时候选序列
    • 已确认符合规则的最终合法组合集合
  2. 终止条件校验:当递归遍历完所有子数组(临时序列长度等于二维数组第一维的规模)时,对当前候选序列做合法性校验:
    • 逐位和集合中所有已存的合法组合计算差异数量
    • 一旦发现某组对比的差异数为1,直接判定当前候选不合法,丢弃
    • 如果所有对比的差异数都≥2,将当前候选加入合法集合
    • 校验时可以提前终止计算:累计差异数到1的时候就不需要继续对比剩余位置,大幅降低运算量
  3. 递归搜索流程:在每个递归位置,遍历当前对应子数组的所有可选元素,将元素拼接到临时候选序列末尾,递归进入下一个位置的搜索,回溯时将选中的元素从临时序列中移除,不影响其他分支的计算

适配性说明

  • 支持任意长度不一致的子数组:递归过程仅遍历当前位置子数组的实际元素,不要求所有子数组的长度相同
  • 完全匹配规模要求:第一维最大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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.25 15:24:04