Swift Program to Find Permutations of a String using Recursion

Swift – Find Permutations of a String using Recursion

In this tutorial, we will learn how to find all permutations of a string using recursion in Swift. We will understand the concept of permutations, write an algorithm, and implement the solution step by step with a complete Swift program and output.

---

What are Permutations?

A permutation is a rearrangement of the elements of a string in all possible orders. For example:

• Permutations of "abc" are "abc", "acb", "bac", "bca", "cab", "cba".
• Permutations of "ab" are "ab", "ba".
• Permutations of "a" are "a".

The total number of permutations of a string with n characters is n! (factorial of n).

---

Algorithm to Find Permutations Using Recursion

1. If the string is empty, return an array containing an empty string.
2. For each character in the string:
   1. Consider it as the first character of the permutation.
   2. Recursively find permutations of the remaining string.
   3. Combine the first character with each permutation of the remaining string.

This approach ensures that all possible arrangements are generated recursively.

---

Step-by-Step Implementation in Swift

1. Define the Base Case

Create a recursive function that returns an array containing an empty string when the input string is empty:

func findPermutations(_ str: String) -> [String] {
    if str.isEmpty {
        return [""]
    }
    return [] // Placeholder for recursive case
}

2. Add the Recursive Case

Implement the logic to generate permutations by fixing each character as the first character and finding permutations of the remaining string:

func findPermutations(_ str: String) -> [String] {
    if str.isEmpty {
        return [""]
    }
    
    var permutations = [String]()
    for (index, char) in str.enumerated() {
        let remaining = str[..<str.index(str.startIndex, offsetBy: index)] + str[str.index(str.startIndex, offsetBy: index + 1)...]
        let subPermutations = findPermutations(String(remaining))
        for subPermutation in subPermutations {
            permutations.append(String(char) + subPermutation)
        }
    }
    return permutations
}

Explanation:

• if str.isEmpty: Returns [""] as the only permutation for an empty string.
• for (index, char) in str.enumerated(): Loops through each character in the string.
• remaining: Generates the remaining string after excluding the current character.
• findPermutations(String(remaining)): Recursively finds permutations of the remaining string.
• String(char) + subPermutation: Prepends the current character to each permutation of the remaining string.

3. Test the Function

Let’s test the function with some example inputs:

// Test cases
let permutations1 = findPermutations("abc")
print("Permutations of 'abc': \(permutations1)")

let permutations2 = findPermutations("ab")
print("Permutations of 'ab': \(permutations2)")

let permutations3 = findPermutations("a")
print("Permutations of 'a': \(permutations3)")

let permutations4 = findPermutations("")
print("Permutations of '': \(permutations4)")

Complete Swift Program

Here’s the complete Swift program:

import Foundation

// Recursive function to find permutations of a string
func findPermutations(_ str: String) -> [String] {
    if str.isEmpty {
        return [""]
    }
    
    var permutations = [String]()
    for (index, char) in str.enumerated() {
        let remaining = str[..<str.index(str.startIndex, offsetBy: index)] + str[str.index(str.startIndex, offsetBy: index + 1)...]
        let subPermutations = findPermutations(String(remaining))
        for subPermutation in subPermutations {
            permutations.append(String(char) + subPermutation)
        }
    }
    return permutations
}

// Test cases
let permutations1 = findPermutations("abc")
print("Permutations of 'abc': \(permutations1)")

let permutations2 = findPermutations("ab")
print("Permutations of 'ab': \(permutations2)")

let permutations3 = findPermutations("a")
print("Permutations of 'a': \(permutations3)")

let permutations4 = findPermutations("")
print("Permutations of '': \(permutations4)")

Output:

Permutations of 'abc': ["abc", "acb", "bac", "bca", "cab", "cba"]
Permutations of 'ab': ["ab", "ba"]
Permutations of 'a': ["a"]
Permutations of '': [""]
Program ended with exit code: 0

Xcode Screenshot: