CODEWITHSUNDEEP
algorithmrecursion
Miguel Guerra
Miguel Guerra

Reputation: 165

String permutations using recursion

For example if I have a string {a, b, c}. I need to print out on the console all the permutations without repeating letters from 1 letter to 3 letters like this:

a b c ab ac abc acb ba bc bac bca ca cb cab cba

How can I write this using recursion?

Upvotes: 1

Views: 219

Answers (1)

Luca Angeletti
Luca Angeletti

Reputation: 59496

If you need all the permutations of the chars into a String you can use a recursive function.

Here's the code in Swift.

func visit(unused:[Character], used: [Character] = [Character]()) -> [String] {
    var result = [String(used)]
    for (index, char) in unused.enumerate() {
        var unused = unused
        unused.removeAtIndex(index)
        var used = used
        used.append(char)
        result = result + visit(unused, used: used)
    }
    return result
}

As you can see the function receives 2 params:

  • unused: represents the list of chars not yet used
  • used: the chars used to build possible element of the ouput. This parameter is optional so if it's not passed to the function, an empty array is used (this is useful for the first invocation).

Test

let word = "abc"
let chars = [Character](word.characters)
print(visit(chars))

["", "a", "ab", "abc", "ac", "acb", "b", "ba", "bac", "bc", "bca", "c", "ca", "cab", "cb", "cba"]

Omitting the empty String

This results also contains the empty String but you can easily omit this value just update the function as shown below.

func visit(unused:[Character], used: [Character] = [Character]()) -> [String] {
    var result = [String]()
    if !used.isEmpty {
        result.append(String(used))
    }
    for (index, char) in unused.enumerate() {
        var unused = unused
        unused.removeAtIndex(index)
        var used = used
        used.append(char)
        result = result + visit(unused, used: used)
    }
    return result
}

Upvotes: 1

Related Questions