Java递归遍历HashMap生成值组合时重复问题的解决方法

我有一个Java HashMap，键为String类型，每个键对应的值是复杂元素ZeugnisNoteMitAa的列表。我需要生成每个键恰好选择一个值的所有可能组合，但当前的递归代码虽能生成所有组合，却会出现重复的组合。

键值组合示例：

• W – w1, w2
• X – x1, x2
• Y – y1, y2
• Z – z1,z2

代码返回的结果中出现了重复组合（如w1, x1, y2, z2重复），我尝试分析递归执行流程但未找到避免重复的递归调用方式，相关代码如下：

private HashMap<String, ZeugnisNoteMitAa> result;

public DeutschCheck(final String bezeichner, final List<String> schulartenList) {
    super(bezeichner, schulartenList);
    mloesungGefunden = false;
    mbeste = new HashMap<>();
    result = new HashMap<>();
    mbearbeitet = new HashMap<>();
}

private void loesungGefunden(HashMap<String, ZeugnisNoteMitAa> map) {
    for (Map.Entry e : map.entrySet()) {
        ZeugnisNoteMitAa note = (ZeugnisNoteMitAa) e.getValue();
        System.out.println(e.getKey() + " " + note.getZeugnisNote().getSchuleFach().getUnterrichtsfach().getAnzeigeform() + " "
                + note.getZeugnisNote().getNote() + "\n");
    }
}

private void doit(HashMap<String, List<ZeugnisNoteMitAa>> map, List<String> keys, int currentKey, int currentValue) {
    if (currentKey >= keys.size()) {
        return;
    } else {
        List<ZeugnisNoteMitAa> currentValues = map.get(keys.get(currentKey));
        if (currentValue < currentValues.size()) {
            result.put(keys.get(currentKey), currentValues.get(currentValue));
            boolean found = true;
            for (String current : keys) {
                if (result.get(current) == null) {
                    found = false;
                }
            }
            if (found) {
                //Print the current selection
                loesungGefunden(result);
            }

            doit(map, keys, currentKey + 1, 0);
            doit(map, keys, currentKey, currentValue + 1);
        }
    }
}

public class ZeugnisNoteMitAa {
    private final ZeugnisNote mZeugnisNote;
    private final SchuelerFachwahlFachAa mAa;
    
    public ZeugnisNoteMitAa(final ZeugnisNote zn, final SchuelerFachwahlFachAa aa) {
        mZeugnisNote = zn;
        mAa = aa;
    }
    
    public ZeugnisNote getZeugnisNote() {
        return mZeugnisNote;
    }
    
    public SchuelerFachwahlFachAa getAa() {
        return mAa;
    }
    
    public SchuelerOberstufe getSchuelerOberstufe() {
        return mAa.getSchuelerFachwahlFach().getSchuelerFachwahl().getSchuelerOberstufe();
    }
}

请问如何修改递归调用以避免组合重复？

问题根源 #

你的递归逻辑存在两个核心问题导致重复：

1. 共享的全局result对象：所有递归调用都修改同一个HashMap，后续递归会覆盖之前的选择，且回溯时未清理当前键的选择，导致旧值残留生成重复组合。
2. 递归分支逻辑混乱：处理当前键的某个值后，同时递归进入下一个键和当前键的下一个值，这种分支方式会让同一组合被多次遍历生成。

修改方案 #

通过两个关键调整解决问题：

• 递归时传递局部组合副本，避免全局共享状态的干扰。
• 调整递归逻辑：遍历当前键的所有值，对每个值递归处理下一个键，直到所有键处理完成再输出组合。

修改后的代码 #

// 移除全局result变量，改用局部传递
private HashMap<String, ZeugnisNoteMitAa> mbeste;
private boolean mloesungGefunden;
private HashMap<String, ?> mbearbeitet;

public DeutschCheck(final String bezeichner, final List<String> schulartenList) {
    super(bezeichner, schulartenList);
    mloesungGefunden = false;
    mbeste = new HashMap<>();
    mbearbeitet = new HashMap<>();
}

private void loesungGefunden(HashMap<String, ZeugnisNoteMitAa> map) {
    for (Map.Entry<String, ZeugnisNoteMitAa> e : map.entrySet()) {
        ZeugnisNoteMitAa note = e.getValue();
        System.out.println(e.getKey() + " " 
                + note.getZeugnisNote().getSchuleFach().getUnterrichtsfach().getAnzeigeform() + " "
                + note.getZeugnisNote().getNote() + "\n");
    }
}

private void doit(HashMap<String, List<ZeugnisNoteMitAa>> map, List<String> keys, int currentKey, HashMap<String, ZeugnisNoteMitAa> currentCombination) {
    // 所有键处理完成，输出当前组合
    if (currentKey >= keys.size()) {
        loesungGefunden(currentCombination);
        return;
    }

    String key = keys.get(currentKey);
    List<ZeugnisNoteMitAa> values = map.get(key);
    
    // 遍历当前键的所有可能值
    for (ZeugnisNoteMitAa value : values) {
        // 创建组合副本，避免修改原对象影响其他分支
        HashMap<String, ZeugnisNoteMitAa> newCombination = new HashMap<>(currentCombination);
        newCombination.put(key, value);
        // 递归处理下一个键
        doit(map, keys, currentKey + 1, newCombination);
    }
}

// 启动组合生成的入口方法
public void startGeneratingCombinations(HashMap<String, List<ZeugnisNoteMitAa>> map, List<String> keys) {
    doit(map, keys, 0, new HashMap<>());
}

public class ZeugnisNoteMitAa {
    private final ZeugnisNote mZeugnisNote;
    private final SchuelerFachwahlFachAa mAa;
    
    public ZeugnisNoteMitAa(final ZeugnisNote zn, final SchuelerFachwahlFachAa aa) {
        mZeugnisNote = zn;
        mAa = aa;
    }
    
    public ZeugnisNote getZeugnisNote() {
        return mZeugnisNote;
    }
    
    public SchuelerFachwahlFachAa getAa() {
        return mAa;
    }
    
    public SchuelerOberstufe getSchuelerOberstufe() {
        return mAa.getSchuelerFachwahlFach().getSchuelerFachwahl().getSchuelerOberstufe();
    }
}

改动说明 #

1. 移除全局状态：用递归参数传递当前组合，每次递归创建新的HashMap副本，确保每个分支的组合独立，不会互相覆盖。
2. 优化终止条件：当currentKey等于键的数量时，说明所有键已完成选择，此时输出组合，而非在中间步骤检查是否填满。
3. 简化遍历逻辑：对当前键的每个值，生成新组合后递归处理下一个键，每个组合只会被生成一次，彻底避免重复。
4. 类型安全优化：修改loesungGefunden的遍历为泛型形式，消除强制类型转换。

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