Random merge of two lists with preserving order

user_3298917 0
Viewed 173

I have two lists, say val l1 = List(1, 2, 3, 4) and val l2 = List(5, 6, 7, 8) and I'd like to merge and shuffle them in a manner that items ordering in the scope of the individual list remain the same, but result list is shuffled.

Let me, please, explain and show a couple of examples:

Desired - List(1, 2, 5, 6, 3, 4, 7, 8) - as you may see original items order from l1 preserved - after 1 goes 2, after 2, goes 3 - skipping items from l2, because we look at the elements from l1 relatively to each other only. And same for l2 after 5 goes 6 and so on.

Desired - List(5, 6, 1, 2, 7, 8, 3, 4) - elements order from l1 and l2 preserved relatevly to each other, similarly to previous example.

Wrong - List(6, 5, 1, 2, 7, 8, 3, 4) - 6 goes before 5, which was not like in l2.

So simple Random.shuffle(l1 ++ l2) won't work for me.

Assume all items in both lists are unique.

Is there any elegant way to do this? Thank you!

scala
3 Answers

This comes up with a different, but correct, result every time I run it.

import scala.util.Random

val l1 = List(1, 2, 3, 4)
val l2 = List(5, 6, 7, 8)

List.unfold((l1,l2)){
  case (Nil, Nil) => None
  case (Nil, hd::tl) => Some((hd, (Nil,tl)))
  case (hd::tl, Nil) => Some((hd, (Nil,tl)))
  case (a, b) => 
    if (Random.nextBoolean()) Some((a.head, (a.tail,b)))
    else                      Some((b.head, (a,b.tail)))
}
user_49931280

A recursive method is one option:

def randomInterleave[T](l1: List[T], l2: List[T]): List[T] = {
  def loop(rem1: List[T], rem2: List[T], res: List[T]): List[T] =
    (rem1, rem2) match {
      case (Nil, _) | (_, Nil) =>
        res.reverse ++ rem1 ++ rem2
      case (hd :: tail, rest) if math.random() < 0.5 =>
        loop(tail, rest, hd +: res)
      case (rest, hd :: tail) =>
        loop(rest, tail, hd +: res)
    }

  loop(l1, l2, Nil)
}

Whether this is elegant or not is a matter of opinion :)

user_76626700

Here's one approach by means of tail-recursion to assemble a new list by iteratively and randomly picking an element from one of the two ordered lists:

def mergeInOrder(list1: List[Int], list2: List[Int]): List[Int] = {
  @scala.annotation.tailrec
  def loop(l1: List[Int], l2: List[Int], acc: List[Int]): List[Int] = (l1, l2) match {
      case (Nil, Nil) => acc
      case (h1::t1, Nil) => loop(t1, l2, h1::acc)
      case (Nil, h2::t2) => loop(l1, t2, h2::acc)
      case (h1::t1, h2::t2) =>
        if (math.random < 0.5) loop(t1, l2, h1::acc) else loop(l1, t2, h2::acc)
  }
  loop(list1, list2, Nil).reverse
}
user_63165080
Related