我正在使用以下代码来生成大小为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]
我正在尝试获取此输出并生成第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]
不会生成,因为在该组合之间,之前或之后没有一组不同的数字。但是,由于在两对[1, 2], [1, 3], [1, 2]
之间存在[1, 3]
组合,因此在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>>>
中。我在StackOverflow上进行了搜索,并看到了几个生成组合的线程(例如this one和this one),但没有解决上面概述的确切情况。
谢谢
最佳答案
我相信我做了你想要的。代码分为四个单独的方法(如果必须为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,在这种情况下,您可以像给定方法一样返回列表列表。之后,我们遍历了所有级别。我们首先检查当前级别是否为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;
}
该循环通过将一个列表与另一个列表进行比较,直到找到两个不同的列表,来检查给定列表是否有效。发生这种情况时,该列表有效,并返回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;
}
此方法采用两个输入列表,并检查其中的元素是否不相等。它遍历两个列表,使元素处于相同的索引,并将它们相互比较。如果它们不相等,则返回true,否则,它完成循环并返回false。
请注意,这仅是概念证明,而不是最终版本。它的很多方面都可以肯定地加以改进,但这是您所要求的工作版本。
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;
}
这是重载的方法,可让您指定所需的级别范围。给定最小和最大级别,它将返回一个新列表,其中包含该范围内(包括端值)的所有级别。正如您所说,作为一个简单的循环,它相对来说比较琐碎。
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]
。如果我升到第二级,我将在您的问题中指定组合。很明显吧?好吧,如果我随后仅使用第2级的结果进入第3级,则我会错过所有包含[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 - 在Java深度生成列表n层的所有组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55487095/