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.lengthget_edges: each letter in the inputis_valid: if a letter is usedused[i] == True, then we skip it...additional states:usedto record which letter is used in the current pathrevert(...additional states): setused[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)
301import 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}
481using 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}
451function 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}
501#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}
42Time 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!).
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.