Kotlin recursive function: Generate permutations of a string

Kotlin Function: Exercise-5 with Solution

Write a Kotlin recursive function to generate all permutations of a given string.

Sample Solution:

Kotlin Code:

fun generatePermutations(input: String): List<String> {
    val permutations = mutableListOf<String>()
    generatePermutationsHelper(input.toCharArray(), 0, permutations)
    return permutations
}

fun generatePermutationsHelper(input: CharArray, index: Int, permutations: MutableList<String>) {
    if (index == input.size - 1) {
        permutations.add(String(input))
        return
    }

    for (i in index until input.size) {
        swap(input, index, i)
        generatePermutationsHelper(input, index + 1, permutations)
        swap(input, index, i) // Backtracking step
    }
}

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

fun main() {
    val input = "code"
    val permutations = generatePermutations(input)
    println("Permutations of '$input':")
    permutations.forEach { 
        print(it)
        print(" ")
    }
}

Sample Output:

Permutations of 'code':
code
coed
cdoe
cdeo
cedo
ceod
ocde
oced
odce
odec
oedc
oecd
doce
doec
dcoe
dceo
deco
deoc
eodc
eocd
edoc
edco
ecdo
ecod

Explanation:

In the above exercise -

• The "generatePermutations()" function initializes an empty list called permutations and calls the helper function "generatePermutationsHelper()" function. The helper function takes the input string as a character array, the current index, and the permutations list as parameters.
• The "generatePermutationsHelper()" function is a recursive function responsible for generating permutations. It checks if the current index is at the last position of the input string. If it is, it adds the generated permutation to the permutations list.
• Otherwise, it iterates through the characters from the current index to the end of the string. For each character, it swaps it with the character at the current index, recursively calls itself with the incremented index, and then swaps the characters back (backtracking step) to restore the original order for the next iteration.
• Finally, in the "main()" function, we define the input string as "code" and generate all permutations using the generatePermutations function. The permutations are then printed to the console.

Kotlin Editor:

Previous: Find the smallest element in an array.
Next: Product of odd numbers in a range.