Looping over All Possible combinations of ArrayList-CodePudding

I want to loop over the same list to process possible combinations of that list. For example : From a list consisting [1,2,3] I want to get an ArrayList which looks like this: [[1,2], [1,3], [2,3]] I am processing a list of nodes instead of integers. For now i am trying something like the following :

ArrayList<ArrayList<Node>> saveList = new ArrayList<ArrayList<Node>>();
for (Node n1 : nodes) 
    ArrayList<Node> saveList2 = new ArrayList<Node>();
    for (Node n2 : nodes) 
        if n2.name == n1.name
            continue;
        saveList2.add(n1).add(n2);
        if (!saveList.containsAll(saveList2)) 
            then process graph;
        else continue;

I don't process the same node and avoid the combination already processed. Is there a better solution ?

CodePudding user response：

Using a combinatorics library may be a bit overkill in your case. Your task is indeed finding combinations of size 2, but the fact that the size is two simplifies it drastically. A good old index-based for-loop does the trick here, with no check for duplicates necessary. Notice how the second loop starts from i 1. Go over the algorithm in a scratchpad and you will see how this avoids duplicates.

List<List<Node>> pairs = new ArrayList<>();
for (int i = 0; i < nodes.size(); i  ) {
  for (int j = i   1; j < nodes.size(); j  ) {
    pairs.add(Arrays.asList(nodes.get(i), nodes.get(j)));
  }
}

CodePudding user response：

If the task is not of academic nature or does not consist of implementing an algorithm, I would use a library and focus on the core of the task the application is supposed to solve. Such a library would be for example combinatoricslib3. Google guava or Apache commons certainly have similar methods. With combinatoricslib3 the solution to your issue above would be a one-liner:

Generator.combination(1,2,3)
        .simple(2)
        .stream()
        .forEach(System.out::println);

Output:

[1, 2]
[1, 3]
[2, 3]

or something like:

List<List<String>> result = Generator.combination("FOO", "BAR", "BAZ")
                                     .simple(2)
                                     .stream()
                                     .collect(Collectors.toList());
System.out.println(result);

to get

[[FOO, BAR], [FOO, BAZ], [BAR, BAZ]]

It works not only for primitive data types like ints or strings as shown above, you can also use your own custom objects and use a list of your objects as a parameter. Assuming you have a Node class:

public class Node {
    String name;
    // getter, setter, toString ...
}

List<Node> nodeList = List.of(new Node("node1"), new Node("node2"), new Node("node3"));
Generator.combination(nodeList)
        .simple(2)
        .stream()
        .forEach(System.out::println);

Output:

[Node(name=node1), Node(name=node2)]
[Node(name=node1), Node(name=node3)]
[Node(name=node2), Node(name=node3)]

To use the lib add the dependency to your pom.xml or download the jar and add to classpath. mvn dependency:

<dependency>
    <groupId>com.github.dpaukov</groupId>
    <artifactId>combinatoricslib3</artifactId>
    <version>3.3.2</version>
</dependency>

CodePudding user response：

Try this.

static <T> List<List<T>> combinations(List<T> list, int n) {
    int length = list.size();
    List<List<T>> result = new ArrayList<>();
    T[] selections = (T[])new Object[n];
    new Object() {
        void select(int start, int index) {
            if (index >= n)
                result.add(List.of(selections));
            else if (start < length){
                selections[index] = list.get(start);
                select(start   1, index   1);
                select(start   1, index);
            }
        }
    }.select(0, 0);
    return result;
}

public static void main(String[] args) {
    List<Integer> list = List.of(1, 2, 3);
    System.out.println(combinations(list, 2));
}

output:

[[1, 2], [1, 3], [2, 3]]