如何判斷一個列表是否是另一個具有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<Integer> sequence = Arrays.asList(1, 3, 6); 
List<Integer> global = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); 

Iterator<Integer> iter = global.iterator(); 
boolean subSequence = sequence.stream().allMatch(itemSequence -> { 
    return Stream.generate(iter::next) 
      .anyMatch(itemGlobal -> itemSequence.equals(itemGlobal)); 
}); 
System.out.println(subSequence); 

它的序列表中[1，3，6]，而序列[1,6，3]扔運作良好一個錯誤java.util.NoSuchElementException。這不是我最終想要達到的。

Answer 2

我認爲你真的接近解決方案（我甚至沒有考慮像這樣的Iterator，所以對你來說是一個加號）。問題是Stream.generate是一個無限的流。

我已經改變了你的代碼。

Iterator<Integer> iter = global.iterator(); 

    boolean subSequence = sequence.stream().allMatch(itemSequence -> { 
     return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iter, Spliterator.ORDERED), false) 
       .anyMatch(itemGlobal -> itemSequence.equals(itemGlobal)); 
    }); 
    System.out.println(subSequence); 

Answer 3

的@潤的回答會涉及調用可迭代::對全球列表<>值spliterator @尤金的變型的一種變體，然後應用結果StreamSupport ::流：

final Spliterator<Integer> spliterator = global.spliterator(); 

final boolean subSequence = sequence.stream().allMatch(
    itemSequence -> StreamSupport.stream(
    spliterator, 
    false 
).anyMatch(itemSequence::equals) 
); 

System.out.println(subSequence); 

Answer 4

房地產功能性解決方案，即不納入可變狀態，很難找到。迄今爲止所有答案都包含可變狀態，這一點可以很好地說明問題。

此外，沒有List.indexOf(T object, int startIndex)操作。爲了說明這一點，那將是多麼有用的是，我們通過helper方法把它定義：

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

Answer 5

我會看到霍爾格回答後添加另一種選擇;但這隻適用於jdk-9 Stream.iterate。

我已經定義了一個輔助方法，以同樣的方式，一點點不同：

private static int fits(List<Integer> global, int elementIndex, int element) { 
    return global.indexOf(element) >= elementIndex ? global.indexOf(element) : -1; 
} 

，然後只用一個int[2]：

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

編輯 霍爾格是正確的，這將只適用於非重複。

我也可以把它寫成重複的，但是現在有fits需要被調用兩次。

boolean allMatch = Stream.iterate(new int[] { 0, 0 }, 
      a -> { 
       return a[0] == sequence.size() ? false : fits(global, sequence.get(a[0])) >= a[1]; 
      }, 
      a -> { 
       int nextFits = fits(global, sequence.get(a[0])); 
       return new int[] { a[0] + 1, nextFits > a[1] ? nextFits + 1 : -1 }; 
      }) 
      .count() == sequence.size();