那些遇到过的问题

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

Ala*_*ook 6 java algorithm math combinations combinatorics

我正在使用以下代码来生成大小为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 ;
}
Run Code Online (Sandbox Code Playgroud)

给定一个1, 2 and 3大小为的值的列表2：

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

combinations(items, 2)
Run Code Online (Sandbox Code Playgroud)

这将产生以下组合：

[1, 2]
[1, 3]
[2, 3]
Run Code Online (Sandbox Code Playgroud)

我正在尝试获取此输出并生成第3个列表，其中先前输出的三行中的每行现在都与其他行合并在一起-仅在此时间顺序上敏感，直到达到“ d”级。我期望结果类似于以下输出：

1级深：

[1, 2]
[1, 3]
[2, 3]
Run Code Online (Sandbox Code Playgroud)

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]
Run Code Online (Sandbox Code Playgroud)

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]]
Run Code Online (Sandbox Code Playgroud)

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]]
Run Code Online (Sandbox Code Playgroud)

请注意，在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]。我们不会[1, 2], [1, 2], [1, 2], [1, 2]在4层深度处生成序列，因为此组合基本上等同于该组合[1, 2]，因为在组合之前，之后或之间没有新的数字集[1, 2]。

简而言之，如何合并一个数字列表列表-最多可扩展到任何数量的级别（仅以1-4为例），但是这次结果是顺序敏感的（因此 [1, 2], [1, 3]不等于[1, 3], [1, 2]）？结果可能存储在中List<List<List<Integer>>>。

我在StackOverflow上进行了搜索，并看到了几个生成组合的线程（例如this和this），但是没有解决上面概述的确切情况。

谢谢

Fis*_*shy 4

我相信我做了你正在寻找的东西。该代码分为四个单独的方法（如果它必须只有 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;
}
Run Code Online (Sandbox Code Playgroud)

这就是大多数算法的作用。首先，就像在您提供的函数中一样，它检查级别是否为 1，在这种情况下您可以只返回列表的列表，就像在给定的方法中一样。之后，我们将循环遍历我们拥有的所有级别。我们首先检查当前级别是否为 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);
    }
}
Run Code Online (Sandbox Code Playgroud)

此方法遍历给定列表内的所有内容，并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;
}
Run Code Online (Sandbox Code Playgroud)

此循环通过将一个列表与另一个列表进行比较来检查给定列表是否有效，直到找到两个不同的列表。当发生这种情况时，列表有效，并返回 true。如果没有，它将永远不会返回，将跳出循环并返回 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;
}
Run Code Online (Sandbox Code Playgroud)

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

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

链接到 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;
}
Run Code Online (Sandbox Code Playgroud)

这是重载方法，允许您指定所需的级别范围。给定最小和最大级别，它将返回一个新列表，其中包含该范围内的所有级别（含）。正如您所说，作为一个简单的循环，它相对琐碎。

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;
}
Run Code Online (Sandbox Code Playgroud)

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

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

我计划进一步重构它，以使其在算法内部进行检查，但这可能需要我花很长时间才能做到这一点。

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;
}
Run Code Online (Sandbox Code Playgroud)

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

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

jDoodle 上的工作版本

归档时间：

查看次数：

312 次

最近记录：

6 年，9 月 前
生成多个列表中的所有组合 44
生成所有可能的组合 - Java 10
更多相关链接
相关归档
如何使用Spring Security检查Java代码中的"hasRole"？ 113
使用Jersey Client忽略自签名的ssl证书 61
java.lang.NoClassDefFoundError:org/apache/commons/fileupload/FileItemFactory 58
在具有正权重的有向图中找出最短长度的循环 16
是否存在容忍微小差异的散列算法？ 10
完全k-partite图中的最大权重k-clique 9
Excel RoundUp与.NET Math.Round 8
理解双递归 7
如何将很长的二进制数转换为十进制？ 6
这是gmpy2中的错误还是我疯了？ 1
难疑归档
使用jQuery从下拉列表(选择框)中获取所选文本 2240
如何按字典值对字典列表进行排序？ 1722
按值对地图<键,值>进行排序 1569
如何离开/退出/停用python virtualenv？ 1461
如何检查Bash中是否设置了变量？ 1417
为什么文本文件以换行符结尾？ 1375
什么是右值,左值,x值,glvalues和prvalues？ 1291
如何重置MySQL中的AUTO_INCREMENT？ 1174
创建将T限制为枚举的通用方法 1122
如何将参数传递给批处理文件？ 1100