正如标题所示，我正在寻找如何实现getNextCombination方法的解决方案，如下面的代码片段所示。
public class Test {
private final List<List<String>> iterators;
/**
* @return null if no combination left
*/
public String[] getNextCombination() {
return null;
}
}
假设属性iterator看起来像
[0]={1,2}
[1]={4,5}
[2]={7,8}
那么对getNextCombination方法的顺序调用应该返回类似于以下的内容:
147
148
157
158
247
248
...
NULL
如何尽可能高效地实现这一点?
谢谢你的帮助。
以下泛型lazy计算所有组合的函数，适用于任意数量的列表或任何其他结构
static Stream<int []> combinationsStream(final int... numElems) {
final int numCombinations = Arrays.stream(numElems) // the number of solutions is
.map(n -> n + 1) // possibles sizes
.reduce(1, (a, b) -> a * b); // product
final int[] queue = Arrays.stream(numElems).map(i -> -1).toArray(); // for every item take n elements
final int[] i = new int[]{0}; // volatile (final) integer
final Function<int [], int []> next = o -> { // compute the next combination
while (true) {
if (i[0] == numElems.length) { // if is the last position
i[0] -= 1; // we will back
return queue; // but it's a combination
}
queue[i[0]] += 1; // take one more of i[0]-th element
if (queue[i[0]] > numElems[i[0]]) // if no more of this
queue[i[0]--] = -1; // reset and go back
else
i[0] += 1; // if not, go forward
}
};
return Stream.iterate(null, next::apply) // iterate getting next over and over
.skip(1) // avoid the seed (null)
.limit(numCombinations); // limit the stream to combs number
}
因为只能处理索引，所以可以这样使用
让你的列表:
// let you list of list (from somewhere)
List<List<String>> iterators = asList(
asList("1", "2"),
asList("4", "5"),
asList("7", "8")
);
(列表可以包含不同数量的元素)
那么，要获得包含所有组合的延迟流，只需将list的列表转换为包含最大索引的数组。// we get combinations in a lazy way simply with
// (you could set this stream in your private class field if you wish)
Stream<int []> lazyCombinations = combinationsStream(iterators.stream()
.mapToInt(g -> g.size() - 1).toArray());
在您的示例中，调用将是combinationsStream(1, 1, 1)，因为每个列表的有效索引是0, 1。
要将一些索引组合转换为String输出，获取索引并连接
// to convert the indexes array to values (and concatenate all) you can write the function
Function<int [], String> toString = indexes -> IntStream
// for each list
.range(0, indexes.length)
// get the indexes[i]-th element
.mapToObj(i -> iterators.get(i).get(indexes[i]))
// and join
.collect(joining());
然后，简单的map从前面的Stream<int []>到Stream<String>，使用函数
// now you can convert your indexes stream to your final combinations stream (all lazy)
Stream<String> lazySolutions = lazyCombinations.map(toString);
你可以在许多方面使用Stream(例如，在Web服务中惰性返回)，但是，如果你希望一个一个地返回，你可以转换为迭代器。
迭代器也是惰性的
// if you need peek combinations on demand (not in a streaming way) convert stream to iterator
Iterator<String> lazyIterator = lazySolutions.iterator();
那么，你只能拿一个
// you can take one by one (e.g. inside a `getNextCombination`)
System.out.println("Only one: " + lazyIterator.next());
或任意数目
// or to the end
lazyIterator.forEachRemaining(System.out::println);
与输出
Only one: 147
148
157
158
247
248
257
258
你可以这样做:
private final List<List<String>> iterators = Arrays.asList(Arrays.asList("1", "2"), Arrays.asList("4", "5"), Arrays.asList("7", "8"));
public void run() {
one("", 0, 0, iterators.size(), iterators.get(0).size()); // begin the iterate over
}
public void iterateOver(String before, int x, int y, int maxX, int maxY) {
List<String> secondList = iterators.get(x); // get Y value list
secondList.forEach((ss) -> {
if(x + 1 < maxX) { // go to next line
iterateOver(before + ss, x + 1, 0, maxX, iterators.get(x + 1).size());
} else if(y + 1 < maxY) {
System.out.println(before + ss); // print result
iterateOver(before + ss, x, y + 1, maxX, maxY); // go to next Y value
} else {
// this is finished
}
});
}
输出:
147
148
157
158
247
248
257
258
警告:Arrays#asList列表不可编辑。
另外，我没有制作完整的getNextCombination方法，因为现在你可以使用这段代码，因为你想实现你喜欢的方式是在一个组合，并进入下一步。