Auf das Vorhandensein einer Unterliste prüfen

Question

Können Sie mir eine ausführende (möglicherweise idiomatische) Möglichkeit geben, um zu überprüfen, ob eine Liste A eine Unterliste einer gegebenen Liste B ist?

z.

isSubList(List(1,2), List(1,2,3,4)) // => true 
isSubList(List(1,2), List(5,6,7,8)) // => false 

Answer 1

Eine Möglichkeit wäre forall zu verwenden und contains:

scala> List(1, 2).forall(List(1, 2, 3, 4).contains) 
res3: Boolean = true 

scala> List(1, 2).forall(List(5, 6, 7, 8).contains) 
res4: Boolean = false 

scala> List(1, 2).forall(List(5, 6, 2, 9).contains) 
res5: Boolean = false 

Beachten Sie, dass dieser Ansatz nicht Bestellung nicht berücksichtigt:

scala> List(1, 2).forall(List(2, 1).contains) 
res6: Boolean = true 

Wahrscheinlich könnte man auch Set s nutzen und intersect aber ich denke, dass dieser Weg vorzuziehen ist.

Answer 2

Wenn Sie bestellen Angelegenheiten containsSlice verwenden können, das anzeigt, ob Sammlungen überprüfen enthält eine vorgegebene Sequenz als Scheibe

def isSubList[A](l1:List[A], l2:List[A]) = l2.containsSlice(l1) 

Answer 3

Eine weitere Lösung:

def isSubList[A](short: List[A], long: List[A]): Boolean = 
    long.tails exists (_.startsWith(short)) 

Allerdings wäre es viel effizienter sein, wenn Listen wurden zuerst in Streams konvertiert:

def isSubList[A](short: List[A], long: List[A]): Boolean = { 
    val sLong = long.toStream 
    val sShort = short.toStream 
    sLong.tails exists (_.startsWith(sShort)) 
} 

Auf diese Weise nicht alle Schwänze h muss generiert werden. Auch startsWith wird in Kurzschluß ausgewertet