Kotlin recursive function: Generate permutations of a string

Last update on February 04 2025 08:26:44 (UTC/GMT +8 hours)

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

Pre-Knowledge (Before You Start!)

Before solving this exercise, you should understand these concepts:

• Recursion: A recursive function calls itself to solve a smaller subproblem until a base case is met.
• Base Case: The recursion stops when the index reaches the last character of the string.
• String Permutations: A permutation is a rearrangement of the characters of a string in all possible orders.
• Swapping Characters: Swapping characters at different positions helps generate different permutations.
• Backtracking: Backtracking ensures that after swapping characters, the original order is restored before the next iteration.

Hints (Try Before Looking at the Solution!)

Here are some hints to help you solve the problem:

• Hint 1: Use recursion to generate permutations by swapping characters.
• Hint 2: Stop recursion when the current index reaches the end of the string.
• Hint 3: Swap each character with the current index to explore all possibilities.
• Hint 4: Use backtracking to revert swaps after each recursive call.
• Hint 5: Store and return all generated permutations in a list.

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.