How to judge whether a list is a sub sequence of another with java8 stream?

Question

For example, I have a long list [1, 2, 3, ..., 10], and a short one [1, 3, 6], then I can tell that the short one is the subsequence of another. On the other hand, the list [1 6 3] is not because it against the order constraint.

Below is my java7 style code for this question:

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

And my wish is to find a java8 stream style to achieve the same result.

Answer 1

Real functional solutions, i.e. not incorporating mutable state, are hard to find. This is best illustrated by the fact that all answer so far incorporate mutable state.

Further, there is no List.indexOf(T object, int startIndex) operation. To illustrate, how useful it would be, let define it via helper method:

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;
}

^{It would be easy to find an alternative implementation without a temporary object, if that’s a concern}

Now, a simple solution using mutable state would be:

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

A functional solution without mutable state requires a value type holding two positions within the two lists. When we use an int[2] array for that, the solution would be:

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