I'm trying to solve a challenge in Kotlin and want to figure out the most efficient way. I must create several lists with all possible combinations of numbers 1,2 and 3. The numbers should sum up to 12. One example is that: (1,2,3,1,2,3). Can someone think of the most efficient way to do that in Kotlin?

Thanks in advance!

CodePudding user response：

Since I was bored.

I suppose one efficient way would be like this. You start with a number, say 1, and take another 1, so you have [1, 1]. If the sum is twelve, you remember the numbers. If it's more than twelve, you discard the last number. And if it's less than twelve, you go two ways; either take yet another number, [1, 1, 1], or increase the last number, [1, 2].

This will give you permutations. To get combinations, do the same, but only ever allow growing sequences of numbers, that is, when a sequence is good, you take [1, 2, 3] but don't take [1, 2, 1].

Here's one implementation. It can be slightly improved further, but should be pretty efficient.

enum class Kind { Permutations, Combinations }

fun getCombinationsOrPermutations(kind: Kind)
        = mutableListOf<List<Int>>().also { result ->
    fun diveIn(numbers: List<Int>) {
        for (number in 1..3) {
            if (kind == Kind.Combinations && numbers.isNotEmpty() && numbers.last() > number) continue
            val newItems = numbers   listOf(number)
            when {
                newItems.sum() > 12 -> return
                newItems.sum() == 12 -> result.add(newItems)
                else -> diveIn(newItems)
            }
        }
    }
    diveIn(emptyList())
}

fun main() {
    getCombinationsOrPermutations(Kind.Permutations)
        .also { println(it.size) }
        .map(::println)
}