如何按需遍历嵌套列表，实现按序返回笛卡尔积组合的getNextCombination方法

核心思路是用多进制进位算法增量生成下一个组合，不需要预先生成全量笛卡尔积，平摊时间复杂度O(1)，空间复杂度只和子列表数量成正比，是目前最高效的实现方式。

完整代码实现 #

import java.util.List;

public class Test {

    private final List<List<String>> iterators;
    // 存储每个子列表当前选中的下标
    private int[] currentIndices;
    // 标记是否还有未返回的组合
    private boolean hasNext;

    public Test(List<List<String>> iterators) {
        this.iterators = iterators;
        // 边界校验：只要有一个子列表为空，笛卡尔积就是空，直接没有结果
        hasNext = !iterators.isEmpty();
        for (List<String> subList : iterators) {
            if (subList.isEmpty()) {
                hasNext = false;
                break;
            }
        }
        if (hasNext) {
            // 初始化下标全为0
            currentIndices = new int[iterators.size()];
        }
    }

    /**
     * @return null if no combination left
     */
    public String[] getNextCombination() {
        if (!hasNext) {
            return null;
        }
        // 1. 先组装当前下标的组合
        String[] result = new String[iterators.size()];
        for (int i = 0; i < iterators.size(); i++) {
            result[i] = iterators.get(i).get(currentIndices[i]);
        }
        // 2. 计算下一个下标（从最后一位开始进位）
        for (int i = currentIndices.length - 1; i >= 0; i--) {
            currentIndices[i]++;
            // 当前位没超出子列表长度，进位完成
            if (currentIndices[i] < iterators.get(i).size()) {
                break;
            }
            // 已经到第一位还溢出，说明没有下一个组合了
            if (i == 0) {
                hasNext = false;
                break;
            }
            // 当前位溢出，置0，继续往前进位
            currentIndices[i] = 0;
        }
        return result;
    }
}

逻辑说明 #

• 初始化时先做边界校验，只要有一个子列表为空，直接标记无可用组合，避免后续无效计算
• 维护的下标数组初始全为0，对应第一个组合
• 每次调用先返回当前下标对应的组合，再按「从后往前进位」的规则计算下一个下标，和十进制加法逻辑完全一致，只是每个位置的进制等于对应子列表的长度
• 当第一位下标溢出时，标记无可用组合，后续调用直接返回null

用你给出的示例测试，返回顺序完全符合预期：第一次调用返回["1","4","7"]，第二次["1","4","8"]，依此类推，直到所有组合返回完成后返回null。

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