N sets

N sets.kt

fun main() {
    println(allCombinations(setOf(1, 2)))
    println(allCombinations(
        setOf(1, 2, 3),
        setOf(4, 5, 6, 7, 8),
        setOf(9, 10)
    ))
    println(allCombinations(
        setOf("abc", "def", "ghi"),
        setOf("aaa", "bbb")
    ))
}

// Given n sets, returns a list of all combinations where the first element is from the first set, the second element is 
// from the second set, and the nth element is from the nth set.
fun <T> allCombinations(vararg sets: Set<T>): List<Set<T>> {
    // Base case with zero sets: ([]) -> []
    // Base case with one set: ([a, b, c, ...]) -> [[a], [b], [c], ...]
    if (sets.isEmpty()) return listOf()
    if (sets.size == 1) return sets[0].map { setOf(it) }

    val retList = mutableListOf<Set<T>>()
    val nestedCombinations = allCombinations(*sets.drop(1).toTypedArray())

    for (i in sets[0]) {
        val mutation = mutableSetOf(i)

        for (j in nestedCombinations) {
            // Unideal, but cannot simply do `retList.add(setOf(i, *j.toTypedArray())` because of reified types
            mutation.addAll(j)
            retList.add(mutation.toSet())
            mutation.removeAll(j)
        }
    }

    return retList
}