Combinations

Algorithms  #algorithms 

A combination is a selection of items from a larger set, where the order of the items does not matter. For example, the combinations of the letters A, B, and C are:

• A
• B
• C
• AB
• AC
• BC
• ABC

There are several ways to calculate the number of combinations of a set of items. One way is to use the combination formula, which is:

C(n, r) = n! / (r!(n - r)!)

where C(n, r) is the number of combinations of n items taken r at a time, n! is the factorial of n (the product of all positive integers from 1 to n), and r! and (n - r)! are the factorials of r and (n - r), respectively.

For example, to find the number of combinations of 3 items taken 2 at a time (also known as a binomial coefficient), we can use the formula like this:

C(3, 2) = 3! / (2!(3 - 2)!) = 3! / (2!1!) = 3 / 2 = 1.5 = 1

There is only 1 combination of 3 items taken 2 at a time: AB.

Another way to calculate combinations is to use the combination table, which is a tabular representation of all the possible combinations of a set of items. For example, the combination table for the set {A, B, C} is:

A	B	C	Combination
1	0	0	A
0	1	0	B
0	0	1	C
1	1	0	AB
1	0	1	AC
0	1	1	BC
1	1	1	ABC

The combination table can be used to quickly determine the number of combinations of a set of items. In this case, there are 7 combinations of 3 items.

//sampleStart
fun main() {
    // click + to see full script
    val k = 2
    val arr = intArrayOf(1, 2, 3, 4)
    val result = IntArray(k)
    printCombinations(arr, result, 0, arr.size.dec(), 0, k)
}
//sampleEnd


fun printCombinations(
    arr: IntArray, result: IntArray, start: Int,
    end: Int, itemsPicked: Int, itemCount: Int
) {
    if (itemsPicked == itemCount) {
        println(result.contentToString())
        return
    }
    val picked = mutableMapOf<Int, Boolean>()
    for (i in start..end) {
        if (picked.getOrDefault(arr[i], false).not()) {
            picked[arr[i]] = true
            result[itemsPicked] = arr[i]
            printCombinations(
                arr, result, i.inc(), end,
                itemsPicked.inc(), itemCount
            )
        }
    }
}