Randomly select n elements from Array

user_8465299 0
Viewed 597

I want to select n unique elements from array where size of my array is normally 1000 and value of n is 3. I want to implement this in iterative algorithm where iterations are around 3000000 and I have to get n unique elements in each iteration. Here are some available solutions I fond but I can not use them due to their draw backs as discussed below.

import scala.util.Random
val l = Seq("a", "b", "c", "d", "e")
val ran = l.map(x => (Random.nextFloat(), x)).sortBy(_._1).map(_._2).take(3)

This method is slower as have to create three arrays and Sorting the array too.

 val list = List(1,2,3,4,5,1,2,3,4,5)
 val uniq = list.distinct
 val shuffled = scala.util.Random.shuffle(uniq)
 val sampled = shuffled.take(n)

Two arrays are generated and Shuffling the large array is slower process.

 val arr = Array.fill(1000)(math.random )
 for (i <- 1 to n; r = (Math.random * xs.size).toInt) yield arr(r)

This is faster tecnique but some times returns same element more than one time. Here is an output.

val xs = List(60, 95, 24, 85, 50, 62, 41, 68, 34, 57)
for (i <- 1 to n; r = (Math.random * xs.size).toInt) yield xs(r)

res: scala.collection.immutable.IndexedSeq[Int] = Vector( 24 , 24 , 41)

It can be observed that 24 is returned 2 times.

How can I change last method to get unique elements? Is there any other more optimal way to perform same task?

random scala
4 Answers

Your examples don't seem to be related (Strings? Ints?) but maybe something like this will work.

import scala.util.Random.nextInt

val limit = 1000  // 0 to 999 inclusive
val n = 3
Iterator.iterate(Set.fill(n)(nextInt(limit)))(_ + nextInt(limit))
        .dropWhile(_.size < n)
        .next()
//res0: Set[Int] = Set(255, 426, 965)
user_49931280

Here is a recursive routine that does the job more efficiently than the other answers.

It builds a list of indices and then checks that the values are distinct. In the rare cases where there are duplicates, these are removed and new values added until there is a distinct set of indices.

The other answers check that the list is distinct each time an element is added.

def randomIndices(arraySize: Int, nIndices: Int): List[Int] = {
  def loop(done: Int, res: List[Int]): List[Int] =
    if (done < nIndices) {
      loop(done + 1, (Math.random * arraySize).toInt +: res)
    } else {
      val d = res.distinct
      val dSize = d.size

      if (dSize < nIndices) {
        loop(dSize, d)
      } else {
        res
      }
    }

  if (nIndices > arraySize) {
    randomIndices(arraySize, arraySize)
  } else {
    loop(0, Nil)
  }
}

randomIndices(xs.size, 3).map(xs)

This should be efficient when the number of elements is small compared to the size of the array.

user_76626700

This is a variant of the Fisher-Yates shuffle. It does not modify the original array, instead it shuffles an array of indices into the original array. A lot of problems can be solved by adding a layer of indirection. It does not shuffle the whole array, it just shuffles num items from the array.

I do not know scala, so this is pseudocode:

partShuffle(num, originalArray)

  // 1. Make a copy of the original array's indices.
  indexAry <- new Array(originalArray.length)
  for (i <- 0; i < originalArray.length; i++)
    indexAry[i] <- i
  end for

  // 2. Shuffle num random unique indices to the front.
  for (i <- 0; i < num; i++)
    // 2.1 New pick from the unpicked part of the array.
    currentPick <- i + random(originalArray.length - i)

    // 2.2 Swap the current pick to the front of the array.
    temp <- indexAry[i]
    indexAry[i] <- indexAry[currentPick]
    indexAry[currentPick] <- temp
  end for

  // 3. Build the return array.
  returnAry <- new Array(num)
  for (i <- 0; i < num; i++)
    returnAry[i] <- originalAry[indexAry[i]]
  end for

  return returnAry

end partShuffle()

As you pick an index, it is swapped to the front of the index array and excluded from further picks. The first pick comes from [0..size-1]; the second pick comes from [1..size-1]; the third pick from [2..size-1] and so on. The selected indices from the original array are returned in a shorter array, length num.

Assumptions:

  • arrays are zero based
  • indexAry is an array of integers
  • returnAry is the same type as originalAry
  • random() is seeded elsewhere in the code
  • random(x) returns an integer from 0 (inclusive) to x (exclusive)
user_8201270

You could generate random indexes between bounds. Generate the bound values by logically splitting the List into n parts.

Example: Given a list of 100 elements and n is 3, the bounds would be (0,32) (33,65) (66,99)

  // Gets random int between "start" and "end"
  def randomInt(start: Int, end: Int): Int =
    start + scala.util.Random.nextInt((end - start) + 1)

  // Generates random int; given limit, total number of chunks and nth chunk
  def randomIntN(limit: Int, n: Int, nth: Int): Int =
    randomInt(
      (((limit / n) * nth) - (limit / n)),
      (((limit / n) * nth) - (if (n == nth) 0 else 1))
    )

  // Generate sequence
  for (
    i <- 1 to n;
    r = randomIntN(xs.size, n, i)
  ) yield xs(r)

Here are some of the outputs

res4: IndexedSeq[Int] = Vector(60, 50, 57)
res5: IndexedSeq[Int] = Vector(60, 85, 34)
res6: IndexedSeq[Int] = Vector(24, 50, 41)
user_12660510
Related