How would you find all permutations of a string?

To find all permutations of a string, one common and efficient method is to use a recursive approach (backtracking). The idea is to fix a character at a time and swap the rest of the characters. This can be implemented as either returning a list of permutations, or printing them out directly. Here is the algorithm in pseudocode form:

- If the string has only one character, return the character itself.

- For each character in the string:

- Fix the character.

- Perform permutation for the remainder of the string.

- Swap the fixed character with the rest of the characters of the string.

## Pseudocode

function Permute(str, leftIndex, rightIndex)
    if leftIndex == rightIndex
        print str
    else
        for i from leftIndex to rightIndex
            str = Swap(str, leftIndex, i)
            Permute(str, leftIndex + 1, rightIndex)
            str = Swap(str, leftIndex, i) // backtrack
 
function Swap(str, i , j)
    temp = str[i]
    str[i] = str[j]
    str[j] = temp
    return str

Here ‘leftIndex‘ starts from index ‘0‘ and ‘rightIndex‘ is ‘str.length - 1‘.

## Python Implementation

To illustrate the above approach, let’s take an example of Python function that generates all permutations for a given string:

def get_permutations(s):
    if len(s) <= 1:
        return [s]

    perms = get_permutations(s[1:])
    first_char = s[0]
    result = []
    for perm in perms:
        for i in range(len(perm)+1):
            result.append(perm[:i] + first_char + perm[i:])
    return result

Given a string of ‘n‘ characters, we can use the formula to calculate the total number of permutations as ‘n!‘ (n factorial), which means ‘n*(n-1)*(n-2)*...*1‘.

In computational complexity terms, the time and space complexity of generating all permutations of a string is ‘O(n*n!)‘, making it quite inefficient on larger strings. This is due to the fact for every of the ‘n!‘ permutations, we do ‘n‘ operations of string concatenation.

However, mathematics provides us with a beautiful solution to this complexity problem, namely Heap’s Algorithm. Its implementation can efficiently generate all permutations of a finite sequence with a time complexity of ‘O(n!)‘. But it needs a deep understanding of permutations group in mathematics which is beyond the scope of this question.