How to Generate All Possible Combinations from Multiple Lists in Java Using Recursion?

Generating All Combinations from Multiple Lists in Java

Generating a single list containing all possible unique combinations from an arbitrary number of lists, each with varying lengths, can be a challenging task. This article explores a Java-based solution using the concept of recursion.

Problem Statement

Given an unknown number of lists, each with an unknown length, the goal is to create a single list comprising all possible combinations of elements from these lists. For instance, with lists X and Y defined as:

X: [A, B, C] 
Y: [W, X, Y, Z]

The expected output would be a list with 12 combinations:

[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

Solution

The solution utilizes recursion to generate all possible combinations. The lists are stored in a list of lists, and a result list is created to hold the permutations. The generatePermutations method takes the list of lists, the result list, a depth parameter, and a string that represents the current permutation as input.

generatePermutations Method

<code class="java">void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
    // Base case: if we've reached the end of the list of lists
    if (depth == lists.size()) {
        result.add(current);
        return;
    }

    // Get the current list at the specified depth
    List<Character> currentList = lists.get(depth);

    // Iterate over each element in the current list
    for (int i = 0; i < currentList.size(); i++) {
        // Recursively call generatePermutations to build permutations
        generatePermutations(lists, result, depth + 1, current + currentList.get(i));
    }
}</code>

The initial call to the generatePermutations method will set the depth to 0 and the current string to an empty string. Each recursive call will increment the depth and concatenate the current character to the current string. The base case is reached when the depth is equal to the number of lists, and at that point, the current permutation is added to the result list.

By utilizing recursion, the generatePermutations method effectively constructs all possible combinations of elements from the input lists and adds them to the result list. This solution is efficient and adaptable to any number or length of input lists.

The above is the detailed content of How to Generate All Possible Combinations from Multiple Lists in Java Using Recursion?. For more information, please follow other related articles on the PHP Chinese website!