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:

letters = 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

function dfs(start_index, path, [...additional states]):
  if is_leaf(start_index):
    report(path)
    return
  for child in get_edges(start_index, [...additional states]):
    # prune if needed
    if not is_valid(child):
      continue
    path.add(child)
    update(start_index)
    if additional states:
      update(...additional states)
    dfs(start_index, path, [...additional states])
    # revert(...additional states) if necessary e.g. permutations
    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: str) -> List[str]:
4    res: List[str] = []
5    path: List[str] = []
6    used = [False] * len(letters)
7
8    def dfs(start_index: int) -> None:
9        if start_index == len(letters):
10            res.append("".join(path))
11            return
12
13        for i, letter in enumerate(letters):
14            # skip used letters
15            if used[i]:
16                continue
17            # add letter to permutation, mark letter as used
18            path.append(letter)
19            used[i] = True
20            dfs(start_index + 1)
21            # remove letter from permutation, mark letter as unused
22            path.pop()
23            used[i] = False
24
25    dfs(0)
26    return res
27
28if __name__ == "__main__":
29    letters = input()
30    res = permutations(letters)
31    for line in sorted(res):
32        print(line)
33
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        res.stream().sorted().forEach(System.out::println);
43    }
44}
45
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
1"use strict";
2
3function permutations(letters) {
4    function dfs(startIndex, path, used, res) {
5        if (startIndex === letters.length) {
6            res.push(path.join(""));
7            return;
8        }
9        for (let i = 0; i < letters.length; i++) {
10            // skip used letters
11            if (used[i]) continue;
12            // add letter to permutation, mark letter as used
13            path.push(letters[i]);
14            used[i] = true;
15            dfs(startIndex + 1, path, used, res);
16            // remove letter from permutation, mark letter as unused
17            path.pop();
18            used[i] = false;
19        }
20    }
21    const res = [];
22    letters = [...letters];
23    dfs(0, [], new Array(letters.length).fill(false), res);
24    return res;
25}
26
27function* main() {
28    const letters = yield;
29    const res = permutations(letters);
30    res.sort();
31    for (const line of res) {
32        console.log(line);
33    }
34}
35
36class EOFError extends Error {}
37{
38    const gen = main();
39    const next = (line) => gen.next(line).done && process.exit();
40    let buf = "";
41    next();
42    process.stdin.setEncoding("utf8");
43    process.stdin.on("data", (data) => {
44        const lines = (buf + data).split("\n");
45        buf = lines.pop();
46        lines.forEach(next);
47    });
48    process.stdin.on("end", () => {
49        buf && next(buf);
50        gen.throw(new EOFError());
51    });
52}
53
1#include <algorithm>
2#include <iostream>
3#include <string>
4#include <vector>
5
6void dfs(int startIndex, std::vector<char>& path, std::vector<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    std::vector<char> path;
29    std::vector<bool> used(letters.size(), false);
30    dfs(0, path, used, res, letters);
31    return res;
32}
33
34int main() {
35    std::string letters;
36    std::getline(std::cin, letters);
37    std::vector<std::string> res = permutations(letters);
38    std::sort(res.begin(), res.end());
39    for (const std::string& line : res) {
40        std::cout << line << '\n';
41    }
42}
43
1package main
2
3import (
4    "bufio"
5    "fmt"
6    "os"
7    "sort"
8)
9
10func permutations(letters string) []string {
11    var res []string
12
13    var dfs func(int, []byte, []bool)
14    dfs = func(startIndex int, path []byte, used []bool) {
15        if startIndex == len(letters) {
16            res = append(res, string(path))
17            return
18        }
19        for i, letter := range letters {
20            // skip used letters
21            if used[i] {
22                continue
23            }
24            // add letter to permutation, mark letter as used
25            path = append(path, byte(letter))
26            used[i] = true
27            dfs(startIndex+1, path, used)
28            // remove letter from permutation, mark letter as unused
29            path = path[:len(path)-1]
30            used[i] = false
31        }
32    }
33
34    dfs(0, []byte{}, make([]bool, len(letters)))
35    return res
36}
37
38func main() {
39    scanner := bufio.NewScanner(os.Stdin)
40    scanner.Scan()
41    letters := scanner.Text()
42    res := permutations(letters)
43    sort.Strings(res)
44    for _, row := range res {
45        fmt.Println(row)
46    }
47}
48

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 strings we generate is n * (n - 1) * (n - 2) * ... * 1, or O(n!) (see math basics if you need a refresher on factorial). Since each string has length n, generating all the strings requires O(n * n!) time.

Space Complexity

The total space complexity is given by the amount of space required by the strings we're constructing. Like the time complexity, the space complexity is also O(n * n!).

Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)