General All Permutations

Given a string of unique letters, find all of its distinct permutations.

Permutation means arranging things with an order. For example, permutations of [1, 2] are [1, 2] and [2, 1]. Permutations are best visualized with trees.

The number of permutations is given by n! (we looked at factorial in Recursion Review). The way to think about permutation is to imagine you have a bag of 3 letters. Initially, you have 3 letters to choose from, you pick one out of the bag. Now you are left with 2 letters, you pick again now there's only 1 letter. The total number of choices is 3*2*1 = 6 (hence we have 6 leaf nodes in the above tree).

Input

  • letters: a string of unique letters

Output

all of its distinct permutations

Examples

Example 1:

Input:

1letters = abc

Output: abc acb bac bca cab cba

Explanation:

All permutations.

Try it yourself

Solution

Permutation is very similar to combination except the same element can NOT be used more than once. For example, if we had picked a for our first letter, we can not use it again for other letters for the same permutation. Here's the state-space tree:

Additional states

This is where we need an additional state to keep track of the letters we have already used. We will introduct a used list to record which letters are already used. used[i] == true means ith letter in the origin list has been used. This variable is passed to the recursive calls to skip the used letters when we branch out.

Revert additional states

Note that in the Generate All Parentheses problem, the additional states openCount and closeCount are copied and in the recurive calls. The used variable, however, is passed by reference in a recursive call. Therefore we have to "undo" the update much like how we undo the update in path variable by popping the last element after the recursive call.

Applying our template

1function dfs(start_index, path, [...additional states]):
2  if is_leaf(start_index):
3    report(path)
4    return
5  for child in get_edges(start_index, [...additional states]):
6    # prune if needed
7    if not is_valid(child):
8      continue
9    path.add(child)
10    update(start_index)
11    if additional states:
12      update(...additional states)
13    dfs(start_index, path, [...additional states])
14    # revert(...additional states) if necessary e.g. permutations
15    path.pop()

Fill in the logics:

  • is_leaf: start_index == letter.length
  • get_edges: each letter in the input
  • is_valid: if a letter is used used[i] == True, then we skip it
  • ...additional states: used to record which letter is used in the current path
  • revert(...additional states): set used[i] = False

Here's the complete code implementation:

1from typing import List
2
3def permutations(letters):
4    def dfs(start_index, path, used, res):
5        if start_index == len(letters):
6            res.append(''.join(path))
7            return
8
9        for i, letter in enumerate(letters):
10            # skip used letters
11            if used[i]:
12                continue
13            # add letter to permutation, mark letter as used
14            path.append(letter)
15            used[i] = True
16            dfs(start_index + 1, path, used, res)
17            # remove letter from permutation, mark letter as unused
18            path.pop()
19            used[i] = False
20
21    res = []
22    dfs(0, [], [False] * len(letters), res)
23    return res
24
25if __name__ == '__main__':
26    letters = input()
27    res = permutations(letters)
28    for line in sorted(res):
29        print(line)
30
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8    private static void dfs(Integer startIndex, List<Character> path, boolean[] used, List<String> res, char[] letters) {
9        if (startIndex == used.length) {
10            // make a deep copy since otherwise we'd be append the same list over and over
11            res.add(path.stream()
12                    .map(e -> e.toString())
13                    .collect(Collectors.joining()));
14            return;
15        }
16        for (int i = 0; i < used.length; i++) {
17            // skip used letters
18            if (used[i])
19                continue;
20            // add letter to permutation, mark letter as used
21            path.add(letters[i]);
22            used[i] = true;
23            dfs(startIndex + 1, path, used, res, letters);
24            // remove letter from permutation, mark letter as unused
25            path.remove(path.size() - 1);
26            used[i] = false;
27        }
28    }
29
30    public static List<String> permutations(String s) {
31        char[] letters = s.toCharArray();
32        List<String> res = new ArrayList<>();
33        dfs(0, new ArrayList<>(), new boolean[letters.length], res, letters);
34        return res;
35    }
36
37    public static void main(String[] args) {
38        Scanner scanner = new Scanner(System.in);
39        String letters = scanner.nextLine();
40        scanner.close();
41        List<String> res = permutations(letters);
42        Collections.sort(res);
43        for (String line : res) {
44            System.out.println(line);
45        }
46    }
47}
48
1using System;
2using System.Collections.Generic;
3
4class Solution
5{
6    private static void Dfs(int startIndex, List<char> path, bool[] used, List<string> res, string letters)
7    {
8        if (startIndex == used.Length)
9        {
10            res.Add(String.Join("", path));
11            return;
12        }
13        for (int i = 0; i < used.Length; i++)
14        {
15            // skip used letters
16            if (used[i]) continue;
17            // add letter to permutation, mark letter as used
18            path.Add(letters[i]);
19            used[i] = true;
20            Dfs(startIndex + 1, path, used, res, letters);
21            // remove letter from permutation, mark letter as unused
22            path.RemoveAt(path.Count - 1);
23            used[i] = false;
24        }
25    }
26
27    public static List<string> Permutations(string letters)
28    {
29        List<string> res = new List<string>();
30        Dfs(0, new List<char>(), new bool[letters.Length], res, letters);
31        return res;
32    }
33
34    public static void Main()
35    {
36        string letters = Console.ReadLine();
37        List<string> res = Permutations(letters);
38        res.Sort();
39        foreach (string line in res)
40        {
41            Console.WriteLine(line);
42        }
43    }
44}
45
1function permutations(letters) {
2    function dfs(startIndex, path, used, res) {
3        if (startIndex == letters.length) {
4            return res.push(path.join(''));
5        }
6        for (let i = 0; i < letters.length; i++) {
7            // skip used letters
8            if (used[i]) continue;
9            // add letter to permutation, mark letter as used
10            path.push(letters[i]);
11            used[i] = true;
12            dfs(startIndex + 1, path, used, res);
13            // remove letter from permutation, mark letter as unused
14            path.pop();
15            used[i] = false;
16        }
17    }
18    const res = [];
19    letters = [...letters];
20    dfs(0, [], new Array(letters.length).fill(false), res);
21    return res;
22}
23
24function* main() {
25    const letters = yield;
26    const res = permutations(letters);
27    res.sort();
28    for (const line of res) {
29        console.log(line);
30    }
31}
32
33class EOFError extends Error {}
34{
35    const gen = main();
36    const next = (line) => gen.next(line).done && process.exit();
37    let buf = '';
38    next();
39    process.stdin.setEncoding('utf8');
40    process.stdin.on('data', (data) => {
41        const lines = (buf + data).split('\n');
42        buf = lines.pop();
43        lines.forEach(next);
44    });
45    process.stdin.on('end', () => {
46        buf && next(buf);
47        gen.throw(new EOFError());
48    });
49}
50
1#include <algorithm> // sort
2#include <iostream> // cin, cout
3#include <string> // getline, string
4#include <vector> // vector
5
6void dfs(int startIndex, std::vector<char> path, bool used[], std::vector<std::string> &res, std::string letters) {
7    if (startIndex == letters.size()) {
8        // make a deep copy, otherwise we'd be appending the same list over and over
9        std::string s(path.begin(), path.end());
10        res.emplace_back(s);
11        return;
12    }
13    for (int i = 0; i < letters.size(); i++) {
14        // skip used letters
15        if (used[i]) continue;
16        // add letter to permutation, mark letter as used
17        path.emplace_back(letters[i]);
18        used[i] = true;
19        dfs(startIndex + 1, path, used, res, letters);
20        // remove letter from permutation, mark letter as unused
21        path.pop_back();
22        used[i] = false;
23    }
24}
25
26std::vector<std::string> permutations(std::string letters) {
27    std::vector<std::string> res;
28    bool used[letters.size()] = { false };
29    dfs(0, {}, used, res, letters);
30    return res;
31}
32
33int main() {
34    std::string letters;
35    std::getline(std::cin, letters);
36    std::vector<std::string> res = permutations(letters);
37    std::sort(res.begin(), res.end());
38    for (const std::string& line : res) {
39        std::cout << line << '\n';
40    }
41}
42

Time Complexity

We have n letters to choose in the first level, n - 1 choices in the second level and so on therefore the number of operation is n * (n - 1) * (n - 2) * ... * 1, or O(n!) (see math basics if you need a refresher on factorial).

Space Complexity

The total space complexity is given by the height of the state-space tree, which is O(n) as we use all n elements.

Still not clear? Submit the part you don't understand to our editors.