Permutations and Combinations Using Kotlin

Permutations and combinations are two fundamental concepts in combinatorics, which is the branch of mathematics concerned with counting and arranging objects.

Permutations are arrangements of objects in a specific order. In other words, a permutation is a selection of objects from a set, where the order of selection matters. For example, if we have three letters A, B, and C, then the permutations of these letters are ABC, ACB, BAC, BCA, CAB, and CBA.

The formula for calculating the number of permutations of n objects taken r at a time is n!/(n-r)!, where n! (n factorial) is the product of all positive integers up to n.

Combinations, on the other hand, are selections of objects where the order doesn’t matter. In other words, a combination is a subset of objects from a set, where the order of selection doesn’t matter. For example, if we have three letters A, B, and C, then the combinations of these letters taken two at a time are AB, AC, and BC.

The formula for calculating the number of combinations of n objects taken r at a time is n!/r!(n-r)!, where n! (n factorial) is the product of all positive integers up to n.

In summary, permutations and combinations are important concepts in combinatorics that help us count and arrange objects in different ways. The main difference between the two is that permutations consider the order of selection, while combinations do not.

here’s a Kotlin code that generates all possible permutations of a given string using recursion:

fun permute(str: CharArray, l: Int, r: Int) {
    if (l == r) {
        println(String(str))
    } else {
        for (i in l..r) {
            str.swap(l, i)
            permute(str, l + 1, r)
            str.swap(l, i)
        }
    }
}

fun CharArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

fun main() {
    val str = "ABC".toCharArray()
    val n = str.size

    println("All permutations of ${String(str)} are:")
    permute(str, 0, n - 1)
}

The permute() function takes three arguments: the string to permute, the starting index l, and the ending index r. The function recursively generates all possible permutations of the string by swapping the characters at different positions.

The base case of the recursion is when l is equal to r. In this case, the function prints the current permutation.

In the recursive case, the function uses a loop to iterate over all possible positions to swap the character at index l with. It then recursively permutes the remaining characters by calling permute() with the updated string and the next index.

The swap() function is a helper function that takes two indices i and j and swaps the characters at those positions in the string.

In the main() function, we define a string to permute and call the permute() function with the string and the starting and ending indices. The function prints all possible permutations of the string.

here’s a Kotlin code that generates all possible combinations of a given string:

fun combine(str: String, start: Int, sb: StringBuilder) {
    for (i in start until str.length) {
        sb.append(str[i])
        println(sb.toString())
        if (i < str.length - 1) {
            combine(str, i + 1, sb)
        }
        sb.setLength(sb.length - 1)
    }
}

fun main() {
    val str = "ABC"
    println("All combinations of $str are:")
    combine(str, 0, StringBuilder())
}

The combine() function takes three arguments: the string to combine, the starting index start, and a StringBuilder to store the current combination. The function recursively generates all possible combinations of the string by appending each character in the string to the StringBuilder.

The base case of the recursion is when the function has appended all characters in the string to the StringBuilder. In this case, the function prints the current combination.

In the recursive case, the function uses a loop to iterate over all possible indices to start the next combination. It then recursively combines the remaining characters by calling combine() with the updated StringBuilder and the next starting index.

The main() function defines a string to combine and calls the combine() function with the string, the starting index of 0, and an empty StringBuilder. The function prints all possible combinations of the string.