Multiple issues using combinations

[mk2301]

I ran into mutliple issues depending on the inputs because of number overflows and too deep recursion. I also got concerned about the memory usage.

For my use case it is enough to stream through the combinations and process one after one (instead of creating all combinations at once and blow my computer).

For this reason I implemented my own (not optimized) combination extensions:

fun <T : Collection<U>, U> T.forEachCombination(combinationSize: Int, callback: (Set<U>) -> Unit) {
    when {
        combinationSize < 2 -> IllegalArgumentException("combinationSize must be at least 2, actual value: $combinationSize")
        this.size <= combinationSize -> callback(this.toSet())
    }

    doForEachCombination(this.toList(), combinationSize) { callback(it) }
}

fun <T : Collection<U>, U> T.combinations(combinationSize: Int): Set<Set<U>> {
    val result = mutableSetOf<Set<U>>()
    forEachCombination(combinationSize) { result.add(it) }
    return result.toSet()
}

private fun <U> doForEachCombination(source: List<U>, combinationSize: Int, depth: Int = 0, idx: Int = 0, tmp: MutableList<U> = source.subList(0, combinationSize).toMutableList(), callback: (Set<U>) -> Unit) {
    for (i in idx..source.size - (combinationSize - depth)) {
        tmp[depth] = source[i]
        when (depth) {
            combinationSize - 1 -> callback(tmp.toSet()) // found new combination
            else -> doForEachCombination(source, combinationSize, depth + 1, i + 1, tmp, callback)
        }
    }
}

It converts the input collection to a List and just iterates through all combinations:
[1,2,3,4] combinations of 2 => [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]

It may not the fastest way, but because of the issues mentioned above it works good for me. The recursion depth equals the size of the combinations. Maybe this implementation is useful for anyone.

[Zordid]

I also ran into the same issue and can propose exactly this kind of change. Tried to get all combinations of 2 out of a set of 600 elements - the currently implementation simply fails as it tries to create the powerset first and filter that down to those of size 2... not an efficient way to do it if we got more than a handful of elements to start with.