Agreed, thanks for sharing.
C# Solution
private static void dfs(List path, bool[] used, List res, char[] letters) {
if (path.Count == used.Length) {
res.Add(String.Join(“”,path));
return;
}
for (int i = 0; i < used.Length; i++) {
// skip used letters
if (used[i])
continue;
// add letter to permutation, mark letter as used
path.Add(letters[i]);
used[i] = true;
dfs(path, used, res, letters);
// remove letter from permutation, mark letter as unused
path.RemoveAt(path.Count - 1);
used[i] = false;
}
}
public static List<string> Permutations(string s)
{
var letters = s.ToCharArray();
var res = new List<string>();
dfs(new List<char>(), new bool[letters.Length], res, letters);
return res;
}
A better (and less verbose) backtracking algorithm will be just thinking how we are do this manually: replacing letters one-by-one - rather than thinking of a tree … With that said, lets take a look on the following:
def permutations(letters: str) → List[str]:
def _dfs(idx=0):
if idx == len(letters):
ret.append(‘’.join(letters[:]))
for i in range(idx, len(letters)):
letters[i], letters[idx] = letters[idx], letters[i]
_dfs(idx+1)
# backtrack
letters[idx], letters[i] = letters[i], letters[idx]
letters = list(letters)
ret = []
_dfs()
return ret
Can someone explain why do we mark the same used index back to false again? Shouldn’t it be put in used only as it is indeed used. I also do not understand why we need to delete the last element of the path?
If we look at the state-space tree, we have n! leafs, and there are n nodes to each leaf, n being number of letters. Although some nodes are used multiple times (a, b, c in this example), complexity still grows at n*n! rate. At each leaf, we copy path (string of n letters) to result. With longer strings it takes longer to copy paths to result, at rate of n.
In the end, the complexity should be O(nnn!) = O(n^2 * n!), right?
Another C# solution, this one using yield pattern
public static List<string> Permutations(string letters)
{
return new List<string>(PermutationsDFS(letters, new bool[letters.Length]));
}
public static IEnumerable<string> PermutationsDFS(string letters, bool[] used)
{
for (int i = 0; i < letters.Length; i++)
{
if (!used[i])
{
used[i] = true;
bool hasPermutations = false;
foreach (var permutation in PermutationsDFS(letters, used))
{
yield return letters[i].ToString() + permutation;
hasPermutations = true;
}
if(!hasPermutations)
{
yield return letters[i].ToString();
}
used[i] = false;
}
}
}
A shorter python solution that doesn’t need an additional “used” boolean. Because all the letters in the “letters” string are unique, we can do dfs on a substring of the original letters.
def permutations(letters: str) → List[str]:
def dfs(letters:str,letter_path:List[str],final_list:List[str]):
if len(letters) == 0:
final_list.append(‘’.join(letter_path))
return
for letter in letters:
new_letters = letters.replace(letter, '') #eliminate the char I already used
dfs(new_letters, letter_path + [letter], final_list)
return final_list
final_list = []
return dfs(letters, [], final_list)
this should be a valid solution, right?
def permutations(letters: str) → List[str]:
letters = list(letters)
result = []
def dfs(index):
if index == len(letters):
result.append(''.join(letters))
return
for j in range(index, len(letters)):
letters[index], letters[j] = letters[j], letters[index]
dfs(index + 1)
letters[index], letters[j] = letters[j], letters[index]
dfs(0)
return result
With globals - easier to reason about for me
def permutations(letters: str) -> List[str]:
def dfs(letter):
# we can *add* all letters, except those already used and the current one
# set construction could be extra cost?
remaining = set(letters) - set(used) - set(letter)
# base case - no more letters left, path is complete, record and return
if remaining == set():
res.append(''.join(used + [letter]))
return
# otherwise - lock in `letter`, and recurse on all remaining
used.append(letter)
for i in remaining:
dfs(i)
used.pop()
# globals for result list, but also for used, so we don't create a copy every time
res = []
used = []
dfs('')
res.sort()
return res
public static List<String> permutations(String letters) {
// WRITE YOUR BRILLIANT CODE HERE
List<String> result = new ArrayList();
dfs(result,new StringBuilder(letters),new StringBuilder());
return result;
}
private static void dfs(List<String> result, StringBuilder letters, StringBuilder current){
if(letters.length() == 0){
result.add(current.toString());
return;
}
for(int i = 0; i < letters.length(); i++){
char c = letters.charAt(i);
current.append(c);
letters.deleteCharAt(i);
dfs(result,new StringBuilder(letters),current);
current.deleteCharAt(current.length() - 1);
letters.insert(0, c);
}
}
Structured Programming JS Solution:
function permutations(letters) {
const arr = letters.split("");
return getPermutations(arr);
}
function getPermutations(letters) {
let results = [];
if (letters.length > 1) {
for (const letter of letters) {
const remaining = letters.filter((a) => a != letter);
const combinations = getPermutations(remaining);
combinations.forEach((combo) => results.push(`${letter}${combo}`));
}
} else {
results.push(letters[0]);
}
return results;
}
Short Python Solution
def permutations(letters: str) -> List[str]:
ret = []
def dfs(l, combo):
if not l:
ret.append(combo)
return
for i in range(len(l)):
dfs(l[:i]+l[i+1:], combo+l[i])
dfs(letters, "")
return ret
backtracking solution is much simpler than the DFS though it may be less intuitive:
function permutations(letters) {
const chars = Array.from(letters);
const results = [];
const backtrack = (f = 0) => {
if (f === letters.length) results.push(chars.join(''));
for (let i = f; i < letters.length; i++) {
[chars[i], chars[f]] = [chars[f], chars[i]];
backtrack(f + 1);
[chars[i], chars[f]] = [chars[f], chars[i]];
}
}
backtrack();
return results;
}
Although it is ‘technically’ a bit less efficient, I wrote a very short python solution:
def permutations(letters: str) -> List[str]:
result = []
def backtrack(bag, path):
if bag == []:
result.append(path)
else:
for index, letter in enumerate(bag):
backtrack(bag[:index] + bag[index + 1:], path + letter)
backtrack(list(letters), '')
return result
Typo: ‘recurive’
s/General All Permutations/Generate All Permutations
My Solution using the “Backtracking - Additional States” template
public static List<String> permutations(String letters) {
// WRITE YOUR BRILLIANT CODE HERE
// Shashi:
List<String> result = new ArrayList<>();
Stack<String> stack = new Stack<>();
Set<Character> set = new HashSet<>();
dfs(letters, stack, set, result);
return result;
}
// Shashi:
public static void dfs (String letters, Stack<String> stack, Set<Character> set, List<String> result) {
if (stack.size() == letters.length()) {
result.add(String.join("", stack));
return;
}
for (char c : letters.toCharArray()) {
// pruning
if (set.contains(c)) continue;
stack.push(String.valueOf(c));
// Update Additional States
set.add(c);
dfs(letters, stack, set, result);
// Revert Additional States
set.remove(c);
stack.pop();
}
}
1 Like
Since we are joining n! paths that are n items long (during the base case), shouldn’t the time complexity be O(n! * n)?
I think the title of this chapter should be, “Generate All Permutations,” not General. Also, here’s my simplified version of the Java solution: as in my previous solutions, I pass a string into dfs instead of a List<String> – this simplifies the concatenation logic; removing letters as I use them means that I can skip the used[] param.
...
import java.util.ArrayList;
class Solution {
private static void dfs(String letters, int numLetters, String path, List<String> result) {
if (path.length() == numLetters) {
result.add(path);
return;
}
int len = letters.length();
for (int i = 0; i < len; i++)
dfs(letters.substring(0, i) + letters.substring(i+1, len), numLetters, path + letters.charAt(i), result);
}
public static List<String> permutations(String letters) {
List<String> result = new ArrayList<>();
dfs(letters, letters.length(), "", result);
return result;
}
...
}
1 Like
Here’s what I managed to come up with:
from typing import List
def permutations(letters: str) -> List[str]:
def get_edges(letter, cur_edges):
return cur_edges.replace(letter, '', 1)
def dfs(level, path, ans, cur_edges):
if level == len(letters):
ans.append(''.join(path))
return
for letter in cur_edges:
path.append(letter)
dfs(level + 1, path, ans, get_edges(letter, cur_edges))
path.pop()
ans = []
dfs(0, [], ans, letters)
return ans