时间戳

首页 > 解决方案 > 如何按需遍历列表列表？

java - 如何按需遍历列表列表？

问题描述

如标题所示，我正在寻找有关如何实现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

如何尽可能高效地实现这一目标？

谢谢你的帮助。

标签： javaalgorithm

解决方案

以下用于计算所有组合的通用惰性函数可以完成这项工作并适用于任意数量的列表或任何其他结构

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

（列表可能包含不同数量的元素）

然后，要获得所有组合的惰性流，只需将列表列表转换为最大索引数组

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

然后，只需将前一个映射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

推荐阅读