String permutations using recursion

Question

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?

Which is it? Backtracking or recursion? I've done similar and it's usually been easier with backtracking. Also, you can do a "recursive" algorithm that uses a global stack but doesn't actually do genuine function recursion. — Craig Estey, Apr 09 '16 at 23:58
Possible duplicate of [Algorithm to generate all possible permutations of a list?](http://stackoverflow.com/questions/2710713/algorithm-to-generate-all-possible-permutations-of-a-list) — jannis, Apr 10 '16 at 00:05
@ChrisMartin The list _does_ have `cb` and `bc` [and did before your edit]. So, probably permutations — Craig Estey, Apr 10 '16 at 00:18

score 1 · Accepted Answer · answered Apr 10 '16 at 00:55

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
}

String permutations using recursion

1 Answers1

Test

Omitting the empty String