How to find all path for the list?

Question

I Have a list like this:

[[A], [B, C, D], [E, F], [G]]

for Java Code init:

 List<List<String>> data = new ArrayList<>();
 data.add(Arrays.asList("A"));
 data.add(Arrays.asList("B", "C", "D"));
 data.add(Arrays.asList("E", "F"));
 data.add(Arrays.asList("G"));

and want get result like bellow:

[[A,B,E,G],[A,B,F,G], [A,C,E,G],[A,C,F,G],[A,D,E,G],[A,D,F,G]]

how to do it ? many thanks.

You are looking for permutations of list in java. look here https://stackoverflow.com/questions/16625220/java-efficient-way-to-find-all-permutation-of-lists?answertab=votes#tab-top — Omri Attiya, Mar 16 '19 at 09:22
@OmriAttiya He's not looking for all permutations. He's looking for all paths through a directed acyclic graph starting at a set of nodes (in this case at only `A`). — marstran, Mar 16 '19 at 09:35

score 0 · Answer 1 · answered Mar 16 '19 at 09:41

You can write a recursive algorithm to solve this. The algorithm moves one layer down in the graph for each recursive call. The gist of it is that you first calculate all paths below the layer you are currently on, then you add all nodes in the current layer to those paths.

Here's some pseudocode to get you going:

paths(input) {
    if input is empty -> return empty // This is your base case

    currentNodes = input[0]
    subPaths = paths(input.tail) // Recursive call with the rest of your input

    if subPaths is empty -> return input // The paths from the last layer is itself

    result = emptyList()
    for all nodes in currentNodes
        for all paths in subPaths
            prepend node to path and add to result

    return result
}

score 0 · Accepted Answer · answered Mar 18 '19 at 06:37

thanks @OmriAttiya. now I show the answer.

it's a Cartesian Product problem.

One line if you use the guava lib

List<List<String>> cartesian = Lists.cartesianProduct(operationTypeList);

cartesianNoRecursive

public static List<List<String>> cartesianNoRecursive(List<List<String>> data) {
    int total = 1;
    for (int i = 0; i < data.size(); i++) {
        total *= data.get(i).size();
    }
    List<List<String>> result =  new ArrayList<>(total);
    for (int i = 0; i < total; i++) {
        result.add(new ArrayList<>());
    }
    int now = 1;
    // used times for every element in one loop
    int itemLoopNum = 1;
    // total  times of every element
    int loopPerItem = 1;
    for (int i = 0; i < data.size(); i++) {
        List<String> temp = data.get(i);
        now = now * temp.size();
        //index of target result
        int index = 0;
        int currentSize = temp.size();
        itemLoopNum = total / now;
        loopPerItem = total / (itemLoopNum * currentSize);
        // index of data
        int dataIndex = 0;
        for (int j = 0; j < temp.size(); j++) {
            for (int k = 0; k < loopPerItem; k++) {
                if (dataIndex == temp.size()) {
                    dataIndex = 0;
                }
                for (int m = 0; m < itemLoopNum; m++) {
                    result.get(index).add(temp.get(dataIndex));
                    index++;
                }
                dataIndex++;

            }
        }
    }
    return result;
}

cartesianRecursive

public static List<List<String>> cartesianRecursive(List<List<String>> list) {
    List<List<String>> result = new ArrayList<List<String>>();
    int numSets = list.size();
    String[] tmpResult = new String[numSets];
    cartesianRecursive(list, 0, tmpResult, result);

    return result;
}

public static void cartesianRecursive(List<List<String>> list, int n, String[] tmpResult, List<List<String>> result) {
    if (n == list.size()) {
        result.add(new ArrayList<String>(Arrays.asList(tmpResult)));
        return;
    }

    for (String i : list.get(n)) {
        tmpResult[n] = i;
        cartesianRecursive(list, n + 1, tmpResult, result);
    }
}

How to find all path for the list?

2 Answers2