Jak losowo wstawić element do listy

Question

Biorąc pod uwagę List[Int]l, jak mogę wstawić losowo nowy element elemdo List[Int]l?

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

Answer 1

Można to zrobić najpierw wybierając losowy indeks na listę, a następnie wstawiając nowy element w tym indeksie . Można to również zrobić w ogólny sposób:

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

Stosowanie:

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)

Możemy użyć tej metody, aby dodać rekurencyjnie kilka elementów:

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

Stosowanie:

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)

Edycja: zgodnie z komentarzem, skuteczniejszym sposobem na to jest dołączenie do obu list i przetasowanie połączonej listy - uwaga niż w ten sposób możesz stracić pierwotną kolejność listy:

import scala.util.Random

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