Combinations of Lists

1

I got some inspiration from Arrow, and asked myself if it is possible to write a a function that allows to collect all combinations of the given list values, something like this:

val s = combinations {
    val i = listOf(0, 1, 2).value()
    val b = listOf(true, false).value()
    val j = listOf("A", "B", "C", "D").value()
    "$i$b$j"
}

// s = [0trueA, 1trueA,... 2falseD]

Turns out it is possible, but it feels a bit hacky:

class ListCombinations private constructor() {
    private val sizes = mutableListOf<BigInteger>()
    private val counters = mutableListOf<Int>()
    private var valueIndex = 0
    private var combination = BigInteger.ZERO
    private val maxCombinations: BigInteger by lazy {
        sizes.reduceOrNull { a, b -> a * b } ?: BigInteger.ZERO
    }

    fun <T> List<T>.value(): T {
        if (combination == BigInteger.ZERO) {
            sizes += size.toBigInteger()
            counters += 0
            return this[0]
        } else {
            return this[counters[valueIndex++]]
        }
    }

    private fun tick(): Boolean = when {
        sizes.isEmpty() -> throw IndexOutOfBoundsException()
        ++combination < maxCombinations -> {
            var c = combination
            for (i in 0..<sizes.size) {
                counters[i] = (c % sizes[i]).toInt()
                c /= sizes[i]
            }
            true
        }

        else -> false
    }

    companion object {
        fun <T> combinations(body: ListCombinations.() -> T): List<T> = try {
            val monad = ListCombinations()
            val result = mutableListOf<T>()
            do {
                monad.valueIndex = 0
                result += monad.body()
            } while (monad.tick())
            result
        } catch (_: IndexOutOfBoundsException) {
            emptyList()
        }
    }
}

I have the feeling I’m overcomplicating things, so please give me feedback regarding the code, and whether you would consider this feature useful.

2

This is an interesting code, but I would definitely call it overcomplicated :stuck_out_tongue_winking_eye:

Good points:

  • It supports any number of lists.
  • It retains type information about each item.

Especially combination of both pros is interesting, because usually we have either the first or the second, but not both.

Bad points:

  • Complicated, DSL which needs to be learned.
  • It creates all lists over and over again, 24 times in the above example. This is really bad and requires explanation in docs, so people don’t for example use heavy code for acquiring the data in the lambda.

Second problem could be potentially fixed by utilizing suspend functions and doing some continuation voodoo, but that will complicate it and make it harder to understand even more.

Alternative?

fun <R, T1, T2> combinations(list1: List<T1>, list2: List<T2>, transform: (T1, T2) -> R): Sequence<R> = sequence {
    for (o1 in list1) {
        for (o2 in list2) {
            yield(transform(o1, o2))
        }
    }
}

fun <R, T1, T2, T3> combinations(list1: List<T1>, list2: List<T2>, list3: List<T3>, transform: (T1, T2, T3) -> R): Sequence<R> = sequence {
    for (o1 in list1) {
        for (o2 in list2) {
            for (o3 in list3) {
                yield(transform(o1, o2, o3))
            }
        }
    }
}

Very simple, even dumb. But very easy to understand, without some hacky DSLs and with good performance. And we almost never really need combination of a variable number of lists. In most cases it will be 2-5 lists and that’s it.

3

You can probably fix the performance problem by changing the DSL to:

combinations {
    val i = value { listOf(0, 1, 2) }
    val b = value { listOf(true, false) }
    val j = value { listOf("A", "B", "C", "D") }
    "$i$b$j"
}

value executes the lambda only during the first iteration, then it re-uses the list provided during that first run. But still, this is complicated :wink:

3 Likes
4

Thank you for the suggestions. The value{ ... } approach wasn’t hard to implement:

class ListCombinations private constructor() {
    private val counters = mutableListOf<Int>()
    private val lists = mutableListOf<List<*>>()
    private var valueIndex = 0
    private var combination = BigInteger.ZERO
    private val maxCombinations: BigInteger by lazy {
        lists
            .map { it.size.toBigInteger() }
            .reduceOrNull { a, b -> a * b } 
            ?: BigInteger.ZERO
    }

    @Suppress("UNCHECKED_CAST")
    fun <T> value(body: () -> List<T>): T {
        if (combination == BigInteger.ZERO) {
            val list = body()
            lists += list
            counters += 0
            return list[0]
        } else {
            return lists[valueIndex][counters[valueIndex++]] as T
        }
    }

    private fun tick(): Boolean = when {
        lists.isEmpty() -> throw IndexOutOfBoundsException()
        ++combination < maxCombinations -> {
            var c = combination
            for (i in 0..<lists.size) {
                val size = lists[i].size.toBigInteger()
                counters[i] = (c % size).toInt()
                c /= size
            }
            true
        }

        else -> false
    }

    companion object {
        fun <T> combinations(body: ListCombinations.() -> T): List<T> = try {
            val monad = ListCombinations()
            val result = mutableListOf<T>()
            do {
                monad.valueIndex = 0
                result += monad.body()
            } while (monad.tick())
            result
        } catch (_: IndexOutOfBoundsException) {
            emptyList()
        }
    }
}