生成深度为 Java 的列表 n 层的所有组合

Question

我正在使用以下代码生成大小为 s 的组合列表：

public static <T extends Comparable<? super T>> List<List<T>> combinations(List<T> items, int size) {
        if (size == 1) {
            List<List<T>> result = new ArrayList<>();
            for (T item : items) {
                result.add(Collections.singletonList(item));
            }
            return result ;
        }
        List<List<T>> result = new ArrayList<>();
        for (int i=0; i <= items.size() - size; i++) {
            T firstItem = items.get(i);
            List<List<T>> additionalItems = combinations(items.subList(i+1, items.size()), size-1) ;
            for (List<T> additional : additionalItems) {
                List<T> combination = new ArrayList<>();
                combination.add(firstItem);
                combination.addAll(additional);
                result.add(combination);
            }
        }
        return result ;
}

给定一个列表，其值为 1, 2 and 3，大小为 2:

List<Integer> items = new ArrayList<Integer>();
items.add(1);
items.add(2);
items.add(3);

combinations(items, 2)

这会产生以下组合：

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

我正在尝试获取此输出并生成第三个列表，其中来自先前输出的三行中的每一行现在都与其他每一行组合 - 只是这次顺序敏感并且最多 'd' 级深。我期待类似于以下输出的结果：

1 级深度：

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

2 级深度：

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

3 级深度：

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

4 级深：

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

请注意，在 2 级深度时，如何不生成组合 [1, 2], [1, 2]，因为在该组之间、之前或之后没有一组不同的数字。然而，在 3 层深度我们生成组合 [1, 2], [1, 3], [1, 2]，因为组合 [1, 3] 存在于两对 [1, 2] 之间。

类似地，在 4 层深度，我们生成序列 [1, 2], [1, 3], [1, 2], [1, 2]，它不等同于序列 [1, 2], [1, 3], [1, 2]，因为有额外的序列 [1, 2] 在 [1, 2], [1, 3], [1, 2] 之后。我们不会在 4 层深度生成序列 [1, 2], [1, 2], [1, 2], [1, 2]，因为该组合本质上等同于 [1, 2]，因为在组合 [1, 2] 之间、之前或之后没有新的数字集。

简而言之，我如何组合数字列表的列表 - 最多可以达到任意数量的深度（1-4 仅用作示例），但这次的结果是 顺序敏感（所以 [1, 2], [1, 3] 不等同于 [1, 3], [1, 2])？结果可能会存储在 List<List<List<Integer>>>.

中

我在 Whosebug 上四处搜索，看到了几个关于生成组合的线程（例如 this one and ），但没有解决上面概述的确切情况。

谢谢

Answer 1

我相信我做出了您想要的东西。代码分为四个独立的方法（如果它必须只有 1 个，你没有做任何区分）：

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    clean(result);
    return result;
}

这就是算法的大部分内容。首先，就像在您提供的函数中一样，它会检查级别是否为 1，在这种情况下，您可以 return 一个列表列表，就像在给定的方法中一样。之后，我们循环遍历我们拥有的许多级别。我们首先检查当前级别是否为 1，在这种情况下，它将执行与调用级别为 1 时相同的操作。接下来我们创建一个名为 newResult 的新列表。这个变量基本上是临时值result，防止并发修改异常。然后我们遍历 result 中已有的每个值。我们根据现有的任何值创建一些新值，并将它们添加到 combined。然后我们把combined加到newResult中，算法就基本结束了。现在，当所有值都相同时，这些循环不算数，例如 [1, 2], [1, 2], [1, 2], [1, 2]。所以我们调用 clean 方法来删除这些情况。

public static <T extends Comparable<? super T>> void clean(List<List<List<T>>> list) {
    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : list) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        list.remove(item);
    }
}

此方法运行遍历给定列表中的所有内容，运行元素上的 check 方法。该方法将在下面进一步解释。如果该元素无效，则将其标记为删除，并在下一个循环中删除。

public static <T extends Comparable<? super T>> boolean check(List<List<T>> list) {
    if(list.size() < 2) return true;

    for(int i = 1; i < list.size(); i++) {
        List<T> previous = list.get(i-1);
        List<T> item = list.get(i);

        if(notEqual(previous, item)){
            return true;
        }
    }

    return false;
}

此循环检查给定列表是否有效，方法是将一个列表与另一个列表进行比较，直到找到两个不相同的列表。发生这种情况时，该列表有效，并且 return 为真。如果不是，它永远不会return，会跳出循环，并且return false.

public static <T extends Comparable<? super T>> boolean notEqual(List<T> a, List<T> b) {
    for(int i = 0; i < Math.min(a.size(), b.size()); i++) {
        T ao = a.get(i);
        T bo = b.get(i);

        if(ao.compareTo(bo) != 0)
            return true;
    }

    return false;
}

此方法接受两个输入列表，并检查它们内部的元素是否不相等。它遍历两个列表，获取同一索引处的元素，并将它们相互比较。如果它们不相等，则 return 为真，否则，它结束循环并且 return 为假。

请注意，这只是一个概念验证，并非最终版本。它的很多方面肯定可以改进，但这是您要求的工作版本。

Link to working version on jDoodle

如果您对它的任何方面有任何疑问，或者想得到任何澄清，请不要犹豫，尽管提问！

编辑： 我已经修改了算法以包含您所要求的内容。这是新代码：

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int minLevel, int maxLevel) {
    List<List<List<T>>> result = new ArrayList<>();

    for(int i = minLevel; i < maxLevel+1; i++) {
        result.addAll(level(items, i));
    }

    return result;
}

这是重载方法，可让您指定所需级别的范围。给定最低和最高级别，它将 return 一个包含该范围内所有级别的新列表，包括在内。正如你所说，它是比较琐碎的，作为一个简单的循环。

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    if(level == 1) {
        for(List<T> item : items) {
            result.add(Collections.singletonList(item));
        }
        return result;
    }

    for(int i = 0; i < level; i++) {
        if(i == 0) {
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>();
        for(List<List<T>> item : result) {
            if(item.size() < i)
                continue;

            List<List<List<T>>> combined = new ArrayList<>();
            List<T> first = item.get(0);
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>();
                List<T> it = items.get(j);
                current.addAll(item);
                current.add(it);

                combined.add(current);
            }

            newResult.addAll(combined);
        }

        result = newResult;
    }

    List<List<List<T>>> removals = new ArrayList<>();
    for(List<List<T>> item : result) {
        if(!check(item))
            removals.add(item);
    }
    for(List<List<T>> item : removals) {
        result.remove(item);
    }

    return result;
}

这里是修改后的方法。我删除了 clean 方法，并将其放在 level 方法中，因为它只被调用了一次。我不认为这真的是可能的，至少在算法期间运行那个 clean 方法的当前代码，因为在这个时间点，它的工作方式是它生成所有可能的组合对于给定的级别，然后转到下一个级别。如果相同的组合被删除，在下一级，这些组合将不会被添加。

这是一个例子：假设我有 [1, 2], [1, 3], [2, 3]。如果我进入二级，我会在你的问题中指定组合。很明显吧？好吧，如果我接着进入第 3 级，只使用第 2 级的结果，我会错过所有包含 [1, 2], [1, 2] [...] 的组合，因为它不在给定的列表中。这是算法的问题，绝对可以改进。

我计划进一步重构它，让它在算法内部进行检查，但这可能会花费我很长时间。

New working version in jDoodle

编辑 2： 在算法中加入 clean 方法实际上比我最初想象的要简单得多。这是带有一些注释的新代码：

public static <T extends Comparable<? super T>> List<List<List<T>>> level(List<List<T>> items, int level) {
    List<List<List<T>>> result = new ArrayList<>();
    for(int i = 0; i < level; i++) {
        if(i == 0) { // If level is 0, we can just add the items as singleton lists to the result
            for(List<T> item : items)
                result.add(Collections.singletonList(item));
            continue;
        }

        List<List<List<T>>> newResult = new ArrayList<>(); // Temporary items that will be added
        for(List<List<T>> item : result) {
            if(item.size() < i) // Make sure we are manipulating items that are on the previous level
                continue;

            List<List<List<T>>> combined = new ArrayList<>(); // The temporary values for this specific item
            for(int j = 0; j < items.size(); j++) {
                List<List<T>> current = new ArrayList<>(); // The current list with the value
                current.addAll(item); // Add the current items from result to the list
                current.add(items.get(j)); // Add the current item from items to the list

                if (i == level-1 && !check(current)) { // If this is the last level, and the current list shouldn't be added, skip adding
                    continue;
                }

                combined.add(current); // Add the current list to the combined values
            }

            newResult.addAll(combined); // Add all of the lists in combined to the new result
        }

        result = newResult; // Make result equal to the new result
    }

    return result;
}

现在它所做的是，当向列表中添加新组合时，它首先检查当前级别是否为最终级别。如果是这样，它实际上会检查列表，如果它无效，它会跳过实际添加它。

我再次计划以更智能的格式完全重写算法，但这段代码现在完全可以工作。

Working version on jDoodle

生成深度为 Java 的列表 n 层的所有组合

Generating All Combinations of List n Levels Deep in Java

java

algorithm

math

combinations

combinatorics