java - java8流如何判断一个列表是否是另一个列表的子序列？

Question

例如，我有一个长列表 [1, 2, 3, ..., 10] 和一个短列表 [1, 3, 6] ，那么我可以说短的是另一个的子序列。另一方面，列表 [1 6 3] 并不是因为它违反了顺序约束。

下面是我针对这个问题的 java7 风格的代码:

List<Integer> sequence = Arrays.asList(1, 3, 6);
List<Integer> global = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
Iterator<Integer> iterGlobal = global.iterator();
boolean allMatch = true;
for(Integer itemSequence: sequence) {
    boolean match = false;
    while(iterGlobal.hasNext()) {
        if(itemSequence.equals(iterGlobal.next())) {
            match = true;
            break;
        }
    }
    if(!match) {
        allMatch = false;
        break;
    }
}
System.out.println(allMatch); //=> true

而我的愿望是找到一个java8流风格来实现同样的结果。

Answer 1

真正的功能解决方案，即不包含可变状态，很难找到。到目前为止，所有答案都包含可变状态这一事实最好地说明了这一点。

此外，没有 List.indexOf(T object, int startIndex) 操作。为了说明它的用途，让我们通过辅助方法定义它:

public static int indexOf(List<?> list, int startIndex, Object o) {
    if(startIndex!=0) list=list.subList(startIndex, list.size());
    int ix=list.indexOf(o);
    return ix<0? -1: ix+startIndex;
}

^{如果担心的话，很容易找到没有临时对象的替代实现}

现在，一个使用可变状态的简单解决方案是:

boolean allMatch = sequence.stream().allMatch(new Predicate<Integer>() {
    int index = 0;
    public boolean test(Integer t) {
        return (index = indexOf(global, index, t)) >=0;
    }
});

没有可变状态的函数式解决方案需要一个值类型在两个列表中占据两个位置。当我们为此使用 int[2] 数组时，解决方案是:

boolean allMatch = Stream.iterate(
        new int[]{ 0, global.indexOf(sequence.get(0)) },
        a -> new int[] { a[0]+1, indexOf(global, a[1], sequence.get(a[0]+1)) }
    )
    .limit(sequence.size())
    .allMatch(a -> a[1]>=0);