Break list when duplicate scala is detected

Question

I have a list of items in Scala, and I'm looking for a way to split the list when a duplicate is detected.

For example: List(x,y,z,e,r,y,g,a)will be converted to List(List(x,y,z,e,r),List(y,g,a)) or List(x,y,z,x,y,z)before List(x,y,z), List(x,y,z) and List(x,y,z,y,g,x)beforeList(x,y,z), List(y,g,x)

Is there a more efficient way than repeating and recording on each item separately?

Answer 1

Fast and dirty O(n)with O(n)extra memory:

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

This solution has a few caveats:

• "", , O(n^2), .
• , , , "duplicate" "-, ". , . , , , 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])) , . , , , , , .

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

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