CODEWITHSUNDEEP
listscalarandom
Valy Dia
Valy Dia

Reputation: 2851

How to insert randomly an element into a List

Given a List[Int] l, how can I insert randomly a new element elem into the List[Int] l?

def randomInsert(l: List[Int], elem: Int): List[Int] = ???

Upvotes: 1

Views: 128

Answers (1)

Valy Dia
Valy Dia

Reputation: 2851

This can be done by first, picking a random index into the list and then inserting the new element at that index. Also this can be done in a generic way:

import scala.util.Random

def randomInsert[A](l: List[A], elem: A): List[A] = {
  val random = new Random
  val randomIndex = random.nextInt(l.length + 1)
  l.patch(randomIndex, List(elem), 0)
}

Usage:

scala>randomInsert(List(1,2,3,4,5),100)
res2: List[Int] = List(1, 2, 3, 4, 5, 100)

scala>randomInsert(List(1,2,3,4,5),100)
res3: List[Int] = List(100, 1, 2, 3, 4, 5)

scala>randomInsert(List(1,2,3,4,5),100)  
res4: List[Int] = List(1, 2, 100, 3, 4, 5)

We can use this method to add recursively several elements:

import scala.util.Random
import scala.annotation.tailrec

def randomInsert[A](l: List[A], elem: A, elems: A*): List[A] = {
  val random = new Random

  @tailrec
  def loop(elemToInsert: List[A], acc: List[A]): List[A] = 
    elemToInsert match {
       case Nil => acc
       case head :: tail =>
         val randomIndex = random.nextInt(acc.length + 1)
         loop(tail, acc.patch(randomIndex, List(head), 0))
    }
  
  loop(elem :: elems.toList, l)
}

Usage:

scala>randomInsert(List(1,2,3,4,5),100,101,102)
res10: List[Int] = List(1, 2, 101, 3, 4, 5, 100, 102)

scala>randomInsert(List(1,2,3,4,5),100,101,102)
res11: List[Int] = List(1, 2, 102, 100, 101, 3, 4, 5)

scala>randomInsert(List(1,2,3,4,5),100,101,102)  
res12: List[Int] = List(1, 2, 3, 4, 100, 5, 102, 101)

Edit: As per comment, an more efficient way to do this is to join both list and to shuffle the combined one - note than by doing so you may lose the original order of the list:


import scala.util.Random

def randomInsert[A](l: List[A], elem: A, elems: A*): List[A] = {
 Random.shuffle((elem :: elems.toList) reverse_::: l)
}

Upvotes: 3

Related Questions