How can I prevent repeating numbers in a random range operator Kotlin?

Question

I have an app in which gives you a certain photo based on an integer being fetched via

class RandomImageLogic(){
    fun retrive(): Int{
        return (1..9).random()
    }
}

However, it is not professional to have a repeated outcome, as I desire a random integer to be fetched each time I call the function in order for the image to be different each time my button is pressed. How can I fetch a new random integer whenever the button calls the function?

Answer 1

I like using Sequences to generate unending streams of values.

In this case we'll have to write custom code, as checking for repeated values is a stateful operation, and while Sequences has a distinct() stateful filter, it applies to all generated values - we only want it to apply to a limited window.

TL;DR:

class RandomImageLogic(
  private val random: Random,
  /** The number of sequential values that must be distinct */
  noRepeatsLimit: Int = 2
) {

  private val sourceValues: List<Int> = (0..9).toList()

  private fun nextValue(vararg exclusions: Int): Int =
    (sourceValues - exclusions.asList()).random(random)

  private val randomInts: Iterator<Int> =
    generateSequence({
      // the initial value just has one random int
      val next = nextValue()
      ArrayDeque(listOf(next))
    }) { previousValues ->
      // generate the next value, excluding previous values
      val nextValue = nextValue(*previousValues.toIntArray())

      // limit the size of previousValues, if necessary
      if (previousValues.size >= noRepeatsLimit)
        previousValues.removeLastOrNull()
      // add the generated value to the beginning of the deque
      previousValues.addFirst(nextValue)

      previousValues
    }
      .map {
        // convert the Sequence to a list of ints,
        // each element is the first item in the deque
        it.first()
      }
      .iterator()

  fun retrieve(): Int {
    return randomInts.next()
  }
}

Testing

Let's write a test first, to make sure our solution works. Kotest has a specific property based testing subproject, and this will let us cover a wide range of test cases very quickly.

So, I ran through the setup, and started setting up the test case.

Seeding RandomImageLogic

First I modified the RandomImageLogic class so that the random selection could be seeded with a provided Random.

import kotlin.random.Random

class RandomImageLogic(private val random: Random) {
  fun retrieve(): Int {
    return (1..9).random(random = random)
  }
}

This will help us to create a Generator for the RandomImageLogic.

Testing all values

Now we can use Kotest to write a property-based test that will assert "for all sequential values, they are different"

import io.kotest.core.spec.style.FunSpec
import io.kotest.property.arbitrary.arbitrary
import io.kotest.property.forAll

class RandomImageLogicTest: FunSpec({

  // This generator will create a new instance of `RandomImageLogic` 
  // and generate two sequential values.
  val sequentialValuesArb = arbitrary { rs ->
    val randomImageLogic = RandomImageLogic(rs.random)

    val firstValue = randomImageLogic.retrieve()
    val secondValue = randomImageLogic.retrieve()

    firstValue to secondValue
  }

  test("expect sequential values are different") {
    forAll(sequentialValuesArb) { (firstValue, secondValue) ->
      firstValue != secondValue
    }
  }

})

Of course, the test fails.

Property failed after 4 attempts

    Arg 0: (1, 1)

Repeat this test by using seed 1210584330919845105

Caused by org.opentest4j.AssertionFailedError: expected:<true> but was:<false>

So let's fix it!

Generating Sequences

As I said earlier, I really like Sequences. They're perfect for this use-case, where we have an infinite source of values.

To demonstrate how to make a Sequence, let's convert the existing code, and use an Iterator to fetch values.

class RandomImageLogic(private val random: Random) {

  private val randomInts =
    // generate a sequence using values from this lambda
    generateSequence { (1..9).random(random = random) }
      // use an iterator to fetch values
      .iterator()

  fun retrieve(): Int {
    return randomInts.next()
  }
}

This hasn't solved the problem yet - the Sequence only generates and provides one value at a time and so cannot do any filtering. Fortunately generateSequence() has an variant with nextFunction: (T) -> T?, where we can determine the next value based on the previous value.

If we use this constructor, and do a bit of refactoring to share the source values, and a util method to generate a next value while filtering out previous values...

  private val sourceValues: List<Int> = (0..9).toList()

  private fun nextValue(vararg exclusions: Int): Int =
    (sourceValues - exclusions.asList()).random(random)

  private val randomInts: Iterator<Int> =
    generateSequence({ nextValue() }) { previousValue ->
      nextValue(previousValue)
    }
      .iterator()

and now if we run the test, it passes!

Test                                    Duration  Result
expect sequential values are different  0.077s    passed

Improvement: more than two distinct sequential values

What happens if you don't just want two sequential values to be distinct, but 3? Or even more? Let's make the 'no-repeated-values' limit configurable, and I think this will demonstrate why Sequences are a good solution.

class RandomImageLogic(
  private val random: Random,
  /** The number of sequential values that must be distinct */
  noRepeatsLimit: Int = 2
) {
  // ...
}

Testing

Once again, let's write a test to make sure things work as expected.

import io.kotest.core.spec.style.FunSpec
import io.kotest.matchers.collections.shouldHaveSize
import io.kotest.matchers.collections.shouldNotContainDuplicates
import io.kotest.property.Arb
import io.kotest.property.arbitrary.int
import io.kotest.property.checkAll
import kotlin.random.Random

class RandomImageLogicTest : FunSpec({

  test("expect arbitrary sequential values are different") {
    checkAll(Arb.int(), Arb.int(1..10)) { seed, noRepeatsLimit->

      val randomImageLogic = RandomImageLogic(Random(seed), noRepeatsLimit)

      val result = List(noRepeatsLimit) { randomImageLogic.retrieve() }

      withClue("Result: $result") {
        result shouldHaveSize noRepeatsLimit
        result.shouldNotContainDuplicates()
      }
    }
  }

})

And of course the test fails.

Property test failed for inputs

0) -459964888
1) 5

Caused by java.lang.AssertionError: Result: [3, 8, 0, 2, 8]
Collection should not contain duplicates

There's lots of options to make a Sequence stateful - again let's just look at one.

Sequence of values

Instead of a sequence of individual values, we can have a sequence where each element is a list of not only the current value, but also previously seen values.

Let's use ArrayDeque to store these values, because it's easy to add and remove values from the start and end.

Again, we use the same generateSequence constructor with a seedFunction and nextFunction - except this time each element is deque which stores all values, and in nextFunction we add new values to the start of the deque, trimming it if it's larger than the window size noRepeatsLimit

  private val randomInts: Iterator<Int> =
    generateSequence({
      // the initial value just has one random int
      val next = nextValue()
      ArrayDeque(listOf(next))
    }) { previousValues ->
      // generate the next value, excluding previous values
      val nextValue = nextValue(*previousValues.toIntArray())

      // limit the size of previousValues, if necessary
      if (previousValues.size >= noRepeatsLimit)
        previousValues.removeLastOrNull()
      // add the generated value to the beginning of the deque
      previousValues.addFirst(nextValue)

      previousValues
    }
      .map {
        // convert the Sequence to a list of ints, 
        // each element is the first item in the deque
        it.first()
      }
      .iterator()

And yup, the test passes!

Test                                              Duration  Result
expect arbitrary sequential values are different  0.210s    passed

Storing state

It's important to think about how state will be stored. 'State' is required by RandomImageLogic to know whether a generated value is distinct.

In the Sequence implementation, it's stored internally, and so is specifically associated with an instance of RandomImageLogic. Maybe your application only has one instance of RandomImageLogic at any one time, in which case the state will always be up to date and will be shared between all invocations.

But what happens if there's more than one instance of RandomImageLogic? Or if there's multi-threading? Or if the RandomImageLogic instance is recreated?

The answers to these depend on the implementation and situation. From your question I suspect that it's not critically important that images never repeat, but I bring this up because it is important to think about.

Answer 2

Pre-fill & random shuffle approach:

class RandomIntIterator(
    private val range: IntRange
) : Iterator<Int> {

    private lateinit var iterator: Iterator<Int>

    init { randomize() }

    fun randomize() {
        iterator = range.shuffled().iterator()
    }

    override fun hasNext() = iterator.hasNext()
    override fun next() = iterator.next()
}

...

val rnd = RandomIntIterator(1..9)
...
// on button click
if (rnd.hasNext()) {
    val num = rnd.next()
    // use num
} else {
    // renew (if needed)
    rnd.randomize()
}

Answer 3

The easy way is to pass in the last random number you received and filter it out.

fun retrive(except: Int): Int{
    return ((1..9).filter {it != except}).random();
}

Answer 4

In your case, this method might not be called extremely often (only when the user clicks a button).

If this method was to be called more often, filter on an IntRange should be used with care (as proposed in @avalerio's answer). This iterates the whole range (unnecessarily costing time) and it would create a temporary ArrayList on every call (creating unnecessary garbage and triggering the garbage collector more often than needed).

Here is a sample object NonRepeatingRandom (you can also implement it as a class if you wish). retrieve (which has been expanded with a max parameter and basic sanity checks) recursivly calls itself again if the same number would be generated twice in a row:

object NonRepeatingRandom {
    private var previous = -1

    fun retrieve(max : Int = 9): Int {
        if(max < 0) {
            error("Only positive numbers")
        }
        if(max <= 1) {
            // There is nothing random about 0 or 1, do not check against previous, just return
            previous = max
            return max
        }

        val rand = (1..9).random()
        return if(rand == previous) {
            retrieve(max) // recursive call if two subsequent retrieve() calls would return the same number
        } else {
            previous = rand // remember last random number
            rand
        }
    }
}

fun main(args: Array<String>) {
    repeat(1000) {
        println(NonRepeatingRandom.retrieve())
    }
}

---

I made a quick-and-dirty performance test, calling my "recursive" method 10 million times and calling the "filter" method 10 million times.

Recursive: 125 ms (10 mio calls)

Filter: 864 ms (10 mio calls)