java在ArrayList的所有可能组合上循环

Question

我想在同一个列表上循环以处理该列表的可能组合。例如：从一个由[1,2,3]组成的列表中，我想得到一个ArrayList，它看起来是这样的：[[1,2], [1,3], [2,3]] 我正在处理节点列表，而不是整数。目前，我正在尝试以下方法：

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;

我不处理同一个节点，并避免已处理的组合。有更好的解决办法吗

Answer 1

如果任务不是学术性质的，或者不包括实现算法，我会使用一个库，关注应用程序应该解决的任务的核心。例如combinatoricslib3就是这样一个库。Google guava或Apache commons当然也有类似的方法。使用combinatoricslib3解决上述问题的方法是一行：

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

输出：

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

或者类似于：

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

得到

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

它不仅适用于基本数据类型，如上文所示的int或string，还可以使用自己的自定义对象并将对象列表用作参数。假设您有一个Node类：

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);

输出：

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

要使用库，请将依赖项添加到pom中。xml或下载jar并添加到类路径。mvn依赖项：

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

Answer 2

在您的情况下，使用组合数学库可能有点过头了。您的任务确实是找到大小为2的组合，但大小为2的事实大大简化了它。 一个好的基于旧索引的for循环在这里实现了这一点，无需检查重复项。注意第二个循环是如何从i+1开始的。在草稿行中检查算法，您将看到这是如何避免重复的

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)));
  }
}

Answer 3

试试这个

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));
}

输出：

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