What is the most efficient way to generate random numbers from a union of disjoint ranges in Kotlin?

Question

I would like to generate random numbers from a union of ranges in Kotlin. I know I can do something like

((1..10) + (50..100)).random()

but unfortunately this creates an intermediate list, which can be rather expensive when the ranges are large.

I know I could write a custom function to randomly select a range with a weight based on its width, followed by randomly choosing an element from that range, but I am wondering if there is a cleaner way to achieve this with Kotlin built-ins.

Answer 1

Suppose your ranges are nonoverlapped and sorted, if not, you could have some preprocessing to merge and sort.

This comes to an algorithm choosing:

• O(1) time complexity and O(N) space complexity, where N is the total number, by expanding the range object to a set of numbers, and randomly pick one. To be compact, an array or list could be utilized as the container.
• O(M) time complexity and O(1) space complexity, where M is the number of ranges, by calculating the position in a linear reduction.
• O(M+log(M)) time complexity and O(M) space complexity, where M is the number of ranges, by calculating the position using a binary search. You could separate the preparation(O(M)) and generation(O(log(M))), if there are multiple generations on the same set of ranges.

For the last algorithm, imaging there's a sorted list of all available numbers, then this list can be partitioned into your ranges. So there's no need to really create this list, you just calculate the positions of your range s relative to this list. When you have a position within this list, and want to know which range it is in, do a binary search.

fun random(ranges: Array<IntRange>): Int {
    // preparation
    val positions = ranges.map {
        it.last - it.first + 1
    }.runningFold(0) { sum, item -> sum + item }

    // generation
    val randomPos = Random.nextInt(positions[ranges.size])
    val found = positions.binarySearch(randomPos)
    // binarySearch may return an "insertion point" in negative
    val range = if (found < 0)  -(found + 1) - 1 else found
    return ranges[range].first + randomPos - positions[range]
}

Answer 2

Short solution

We can do it like this:

fun main() {
    println(random(1..10, 50..100))
}

fun random(vararg ranges: IntRange): Int {
    var index = Random.nextInt(ranges.sumOf { it.last - it.first } + ranges.size)
    ranges.forEach {
        val size = it.last - it.first + 1
        if (index < size) {
            return it.first + index
        }
        index -= size
    }

    throw IllegalStateException()
}

It uses the same approach you described, but it calls for random integer only once, not twice.

Long solution

As I said in the comment, I often miss utils in Java/Kotlin stdlib for creating collection views. If IntRange would have something like asList() and we would have a way to concatenate lists by creating a view, this would be really trivial, utilizing existing logic blocks. Views would do the trick for us, they would automatically calculate the size and translate the random number to the proper value.

I implemented a POC, maybe you will find it useful:

fun main() {
    val list = listOf(1..10, 50..100).mergeAsView()
    println(list.size) // 61
    println(list[20]) // 60
    println(list.random())
}

@JvmName("mergeIntRangesAsView")
fun Iterable<IntRange>.mergeAsView(): List<Int> = map { it.asList() }.mergeAsView()

@JvmName("mergeListsAsView")
fun <T> Iterable<List<T>>.mergeAsView(): List<T> = object : AbstractList<T>() {
    override val size = [email protected] { it.size }

    override fun get(index: Int): T {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException(index)
        }

        var remaining = index
        [email protected] { curr ->
            if (remaining < curr.size) {
                return curr[remaining]
            }
            remaining -= curr.size
        }

        throw IllegalStateException()
    }
}

fun IntRange.asList(): List<Int> = object : AbstractList<Int>() {
    override val size = endInclusive - start + 1

    override fun get(index: Int): Int {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException(index)
        }
        return start + index
    }
}

This code does almost exactly the same thing as short solution above. It only does this indirectly.

Once again: this is just a POC. This implementation of asList() and mergeAsView() is not at all production-ready. We should implement more methods, like for example iterator(), contains() and indexOf(), because right now they are much slower than they could be. But it should work efficiently already for your specific case. You should probably test it at least a little. Also, mergeAsView() assumes provided lists are immutable (they have fixed size) which may not be true.

It would be probably good to implement asList() for IntProgression and for other primitive types as well. Also you may prefer varargs version of mergeAsView() than extension function.

As a final note: I guess there are libraries that does this already - probably some related to immutable collections. But if you look for a relatively lightweight solution, it should work for you.