當發現重複時拆分列表scala

Question

我有一個Scala中的元素列表，我正在尋找一種方法來在發現重複時拆分列表。

例如：List(x,y,z,e,r,y,g,a)將被轉換爲List(List(x,y,z,e,r),List(y,g,a)) 或List(x,y,z,x,y,z)到List(x,y,z), List(x,y,z) 並List(x,y,z,y,g,x)到List(x,y,z), List(y,g,x)

是否有比迭代和，並分別cheking每個元素的更有效的方法是什麼？

Answer 1

快速和髒O(n)使用O(n)額外的存儲器：

import scala.collection.mutable.HashSet 
import scala.collection.mutable.ListBuffer 

val list = List("x", "y", "z", "e", "r", "y", "g", "a", "x", "m", "z") 

var result = new ListBuffer[ListBuffer[String]]() 
var partition = new ListBuffer[String]() 

list.foreach { i => 
    if (partition.contains(i)) { 
     result += partition 
     partition = new ListBuffer[String]() 
    } 
    partition += i 
} 

if (partition.nonEmpty) { 
    result += partition 
} 
result 

ListBuffer（ListBuffer（X，Y，Z，E，R），ListBuffer（Y，G，A，X，M，Z ））

Answer 2

您基本上需要迭代查找表。我可以提供有關以下不可變和功能性tailrec實現的幫助。

import scala.collection.immutable.HashSet  
import scala.annotation.tailrec 

val list = List("x","y","z","e","r","y","g","a", "x", "m", "z", "ll") 

def splitListOnDups[A](list: List[A]): List[List[A]] = { 
    @tailrec 
    def _split(list: List[A], cList: List[A], hashSet: HashSet[A], lists: List[List[A]]): List[List[A]] = { 
    list match { 
     case a :: Nil if hashSet.contains(a) => List(a) +: (cList +: lists) 
     case a :: Nil => (a +: cList) +: lists 
     case a :: tail if hashSet.contains(a) => _split(tail, List(a), hashSet, cList +: lists) 
     case a :: tail => _split(tail, a +: cList, hashSet + a, lists) 
    } 
    } 

    _split(list, List[A](), HashSet[A](), List[List[A]]()).reverse.map(_.reverse) 
} 

def splitListOnDups2[A](list: List[A]): List[List[A]] = { 
    @tailrec 
    def _split(list: List[A], cList: List[A], hashSet: HashSet[A], lists: List[List[A]]): List[List[A]] = { 
    list match { 
     case a :: Nil if hashSet.contains(a) => List(a) +: (cList +: lists) 
     case a :: Nil => (a +: cList) +: lists 
     case a :: tail if hashSet.contains(a) => _split(tail, List(a), HashSet[A](), cList +: lists) 
     case a :: tail => _split(tail, a +: cList, hashSet + a, lists) 
    } 
    } 

    _split(list, List[A](), HashSet[A](), List[List[A]]()).reverse.map(_.reverse) 
} 

splitListOnDups(list) 
// List[List[String]] = List(List(x, y, z, e, r), List(y, g, a), List(x, m), List(z, ll)) 

splitListOnDups2(list) 
// List[List[String]] = List(List(x, y, z, e, r), List(y, g, a, x, m, z, ll)) 

Answer 3

一個聲明尾遞歸版本（但不是很有效，因爲contains名單上的）

var xs = List('x','y','z','e','r','y','g','a') 

def splitAtDuplicates[A](splits: List[List[A]], right: List[A]): List[List[A]] = 
    if (right.isEmpty)// done 
    splits.map(_.reverse).reverse 
    else if (splits.head contains right.head) // need to split here 
    splitAtDuplicates(List()::splits, right) 
    else // continue building current sublist 
    splitAtDuplicates((right.head :: splits.head)::splits.tail, right.tail) 

加快步伐了Set來跟蹤我們到目前爲止看到：

def splitAtDuplicatesOptimised[A](seen: Set[A], 
            splits: List[List[A]], 
            right: List[A]): List[List[A]] = 
    if (right.isEmpty) 
    splits.map(_.reverse).reverse 
    else if (seen(right.head)) 
    splitAtDuplicatesOptimised(Set(), List() :: splits, right) 
    else 
    splitAtDuplicatesOptimised(seen + right.head, 
           (right.head :: splits.head) :: splits.tail, 
           right.tail) 

Answer 4

該解決方案提供的一些注意事項：

• 雖然我認爲它比蠻力的O(n^2)更好，但我並沒有對「表現」做出聲明。
• 這是假設你在發現重複時分裂，其中「重複」意味着「在前面的分裂中存在的東西」。我只通過檢查最後一段來作弊。原因是我認爲它澄清了如何使用foldLeft一點，這是一個自然的方式去做這件事。
• 這裏的一切都是相反的，但維護秩序。這可以很容易地糾正，但增加了一個額外的O(n)（累計）調用，可能實際上並不需要（取決於你在做什麼）。

下面是代碼：

def partition(ls: List[String]): List[ListSet[String]] = { 
    ls.foldLeft(List(ListSet.empty[String]))((partitionedLists, elem:String) => { 
    if(partitionedLists.head.contains(elem)) { 
     ListSet(elem) :: partitionedLists 
    } else { 
     (partitionedLists.head + elem) :: partitionedLists.tail 
    } 
    }) 
} 

partition(List("x","y","z","e","r","y","g","a")) 
// res0: List[scala.collection.immutable.ListSet[String]] = List(ListSet(r, e, z, y, x), ListSet(a, g, y)) 

我使用ListSet獲得Set和排序，這是適用於您的使用案例雙方的利益。

foldLeft是一個函數，它接受一個累加器值（在本例中爲List(ListSet.empty[String])），並在它通過集合中的元素時對其進行修改。如果我們像這裏所做的那樣將累加器構造成段的列表，那麼當我們完成時它將具有原始列表的所有有序段。