How do you write a function to divide the input list into three sublists?-CodePudding

Write a function to divide the input list into three sublists. The first sub-list is to include all the elements whose indexes satisfy the equation i mod 3 = 1. The second sub-list is to include all the elements whose indexes satisfy the equation and mod 3 = 2. The third sub-list is to contain the remaining elements. The order of the elements must be maintained. Return the result as three lists. Write a function using tail and non-tail recursion.

My attempt: I’m very confused in how to increase index so it can go through the list, any recommendation about how to make it recursive with increasing index each time?

        def divide(list: List[Int]): (List[Int], List[Int], List[Int]) = {
          var index:Int =0
          def splitList(remaining: List[Int], firstSubList: List[Int], secondSubList: List[Int], thirdSubList: List[Int], index:Int): (List[Int], List[Int], List[Int]) = {
            if(remaining.isEmpty) {
              return (List[Int](), List[Int](), List[Int]())
            }

            val splitted = splitList(remaining.tail, firstSubList, secondSubList, thirdSubList, index)

            val firstList = if (index % 3 == 1) List() ::: splitted._1 else splitted._1
            val secondList = if (index % 3 == 2) List() ::: splitted._2 else splitted._2
            val thirdList = if((index% 3 != 1) && (index % 3 != 2)) List() ::: splitted._3 else splitted._3
            index  1
            (firstSubList ::: firstList, secondSubList ::: secondList, thirdSubList ::: thirdList)

          }

          splitList(list, List(), List(), List(), index 1)
        }

      println(divide(List(0,11,22,33)))

CodePudding user response：

Here's one approach using a simple recursive function to compose a generalized Map of Lists:

def splitList(list: List[Int], n: Int): Map[Int, List[Int]] = {
  @scala.annotation.tailrec
  def loop(zls: List[(Int, Int)], lsMap: Map[Int, List[Int]]): Map[Int, List[Int]] =
    zls match {
      case Nil =>
        lsMap.map{ case (i, ls) => (i, ls.reverse) }
      case (x, i) :: rest =>
        val j = i % n
        loop(rest, lsMap   (j -> (x :: lsMap.getOrElse(j, Nil))))
    }
  loop(list.zipWithIndex, Map.empty[Int, List[Int]])
}

splitList(List(0, 11, 22, 33, 44, 55, 66), 3)
// Map(0 -> List(0, 33, 66), 1 -> List(11, 44), 2 -> List(22, 55))

CodePudding user response：

To do this in real life, just label each value with its index and then group by that index modulo 3:

def divide[T](list: List[T]) = {
  val g = list.zipWithIndex.groupMap(_._2 % 3)(_._1)

  (g.getOrElse(1, Nil), g.getOrElse(2, Nil), g.getOrElse(0, Nil))  
}

If you insist on a recursive version, it might look like this:

def divide[T](list: List[T]) = {
  def loop(rem: List[T]): (List[T], List[T], List[T]) =
    rem match {
      case a::b::c::tail =>
        val rem = loop(tail)
        (b  : rem._1, c  : rem._2, a  : rem._3)
      case a::b::Nil =>
        (List(b), Nil, List(a))
      case a::Nil =>
        (Nil, Nil, List(a))
      case Nil =>
        (Nil, Nil, Nil)
    }

  loop(list)
}

Tail recursion would look like this:

def divide[T](list: List[T]) = {
  @annotation.tailrec
  def loop(rem: List[T], res: (List[T], List[T], List[T])): (List[T], List[T], List[T]) =
  rem match {
    case a::b::c::tail =>
        loop(tail, (res._1 :  b, res._2 :  c, res._3 :  a))
    case a::b::Nil =>
        (res._1 :  b, res._2, res._3 :  a)
    case a::Nil =>
        (res._1, res._2, res._3 :  a)
    case Nil =>
        res
  }

  loop(list, (Nil, Nil, Nil))
}

And if you care about efficiency, this version would build the lists in the other order and reverse them when returning the result.

CodePudding user response：

Your problem is that you put index 1 into a wrong place. Try swapping it around: put index 1 into the call where you have index, and index into the other one. Also remove the "standalone" index 1 statement in the middle, it doesn't do anything anyway.

That should make your code work ... but it is still not very good. A couple of problems with it (besides it being badly structured, non-idiomatic, and hard to read, which is kinda subjective):

It it is not tail-recursive, and effectively, creates another copy of the entire list on stack. This may be problematic when the list is long.
It concatenates (potentially long) lists. This is a bad idea. List in scala is a singly linked list, you have it's head readily available, but to get to the end, you need to spend O(N) cycles, iterating through each node. Thus things like foo:::bar in a iterative function instantly make any algorithm (at least) quadratic.

The usual "trick" to avoid the last problem is prepending elements to output one-by-one, and then reversing the result in the end. The first one can be avoided with tail-recursion. The "non-idiomatic" and "hard to read" problems are mostly addressed by using match statement in this case:

    def split3(
      in: List[Int], 
      one: List[Int], 
      two: List[Int], 
      three: List[Int], 
      index: Int = 0
    } = (in, index % 3) match {
      case (Nil, _) => (one.reverse, two.reverse, three.reverse)
      case (head::tail, 1) => split3(tail, head::one, two, three, index 1) 
      case (head::tail, 2) => split3(tail, one, head::two, three, index 1)
      case (head::tail, _) => split3(tail, one, two, head::three, index 1)
    }

Now, this is a fine solution, albeit a little repetitive to my demanding eye ... But if want to be clever and really unleash the full power of scala standard library, forget recursion, you don't really need it in this case.

If you knew that number of elements in the list was always divisible by 3, you could just do list.grouped(3).toSeq.transpose: break the list into groups of three (each group will have index%3=0 as first element, index%3=1 as second, index%3=2 as the third), and then transpose will turn a list of lists of 3 into a list of three lists where the first one contains all the first elements, the second - all the seconds etc. (I know, you wanted them in a different order, but that's trivial). If you are having trouble understanding what I am talking about, just try running it on some lists, and look at the results.

This would be a really elegant solution ... if it worked :/ The problem is, that it only does when you have 3*n elements in the original list. If not, transpose will fail on the last element if it doesn't have 3 elements like all others. Can we fix it? Well ... that's where the cleverness comes in.

   val (triplets, tails) = list.grouped(3).toSeq.partition(_.size == 3) 
   triplets 
     .transpose
     .padTo(3, Nil)
     .zip(tails.flatten.map(Seq(_)).padTo(3, Nil))
     .map { case (head, tail) => head    tail }

Basically, it is doing the same thing as the one-liner I described above (break into groups of 3 and transpose), but adds special handling for the case when the last group has less than three elements - it splits it out and pads with required number of empty lists, then just appends the result to transposed triplets.