如何实现基于Configuration类step字段的多配置项全组合排列算法？

Hey there! Let's work through this configuration combination problem together. You're absolutely right that nested loops won't cut it here—since the number of Configuration objects can be dynamic (2, 3, or more), a recursive approach is perfect for handling variable-depth combinations. Let's break down how to implement this.

First, Let's Understand the Core Problem #

We need to generate the Cartesian product of all possible values from each Configuration object. For each config, we first generate all valid values (from start to end, incrementing by step), then combine every value from the first config with every value from the second, and so on for all configs.

Step 1: Helper Method to Generate Values for a Single Configuration #

First, let's write a small helper that takes one Configuration and returns all its valid integer values:

private List<Integer> generateConfigValues(Configuration config) {
    List<Integer> values = new ArrayList<>();
    int currentValue = config.getStart();
    // Make sure we include the end value (note the <= instead of <)
    while (currentValue <= config.getEnd()) {
        values.add(currentValue);
        currentValue += config.getStep();
        // Optional: Add a check here to prevent infinite loops if step is 0, based on your business rules
    }
    return values;
}

Step 2: Recursive Implementation #

Recursion works here by building combinations incrementally. We'll track which config we're currently processing, and the combination we've built so far. When we've processed all configs, we print the final combination.

Here's the full recursive solution:

public void print(List<Configuration> configurations) {
    // First, pre-generate all values for each configuration
    List<List<Integer>> allConfigValues = new ArrayList<>();
    for (Configuration config : configurations) {
        allConfigValues.add(generateConfigValues(config));
    }
    // Start the recursive combination generation
    generateAndPrintCombinations(allConfigValues, 0, new ArrayList<>());
}

private void generateAndPrintCombinations(List<List<Integer>> allValues, int currentConfigIndex, List<Integer> currentCombination) {
    // Base case: We've processed all configurations—print the combination
    if (currentConfigIndex == allValues.size()) {
        // Convert the integer list to a comma-separated string
        String comboString = String.join(",", currentCombination.stream().map(String::valueOf).toList());
        System.out.println(comboString);
        return;
    }

    // Iterate over all values of the current configuration
    for (Integer value : allValues.get(currentConfigIndex)) {
        // Add the current value to our combination
        currentCombination.add(value);
        // Recurse to process the next configuration
        generateAndPrintCombinations(allValues, currentConfigIndex + 1, currentCombination);
        // Backtrack: Remove the last value to try the next one for this configuration
        currentCombination.remove(currentCombination.size() - 1);
    }
}

How This Works #

1. Pre-generate Values: We first create a list of lists, where each inner list contains all valid values for one Configuration.
2. Recursive Combination:
   • The base case triggers when we've processed every config—we print the completed combination.
   • For each value in the current config, we add it to our ongoing combination, then recurse to process the next config.
   • After recursion returns, we backtrack (remove the last value) to try the next value for the current config. This ensures we cover every possible combination.

Alternative: Iterative Approach (No Recursion) #

If you prefer to avoid recursion, you can build combinations iteratively by expanding the list of combinations one config at a time:

public void printIterative(List<Configuration> configurations) {
    // Start with an empty combination as the base
    List<List<Integer>> combinations = new ArrayList<>();
    combinations.add(new ArrayList<>());

    for (Configuration config : configurations) {
        List<Integer> currentValues = generateConfigValues(config);
        List<List<Integer>> newCombinations = new ArrayList<>();

        // For each existing combination, pair it with every value from the current config
        for (List<Integer> existingCombo : combinations) {
            for (Integer value : currentValues) {
                List<Integer> newCombo = new ArrayList<>(existingCombo);
                newCombo.add(value);
                newCombinations.add(newCombo);
            }
        }

        // Replace the old combinations with the newly expanded ones
        combinations = newCombinations;
    }

    // Print all final combinations
    for (List<Integer> combo : combinations) {
        System.out.println(String.join(",", combo.stream().map(String::valueOf).toList()));
    }
}

Testing with Your Examples #

Both implementations will produce exactly the output you expected for your sample scenarios. For example, with 3 configs, they'll generate all 2×2×3=12 combinations correctly.

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