用递归回溯。为什么代码有效
Backtracking with recursion. Why is the code working
你能帮我理解下面的代码片段吗？该注释说它正在通过回溯进行字符串排列，但我就是不明白。我不明白嵌套的 for 循环在做什么。我试着用“猫”来跟随代码。那么排列集没有吗？
public static Set<String> getPermutations(String inputString) {
if(inputString.length() <= 1) {
return new HashSet<>(Collections.singletonList(inputString));
}
String allCharsExceptLast = inputString.substring(0, inputString.length()-1);
char lastChar = inputString.charAt(inputString.length()-1);
Set<String> permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);
Set<String> permutations = new HashSet<>();
for(String permutationOfAllCharsExceptLast: permutationsOfAllCharsExceptLast) {
for(int position = 0; position <= allCharsExceptLast.length(); position++) {
String permutation = permutationOfAllCharsExceptLast.substring(0, position) + lastChar +
permutationOfAllCharsExceptLast.substring(position);
permutations.add(permutation);
}
}
return permutations;
}
}
算法的工作原理如下：
基本情况：当字符串只包含一个字符时，return只包含一个字符串的集合：这是唯一可能的排列。
解决少一个字符的问题：获取缺少原始最后一个字符的较短字符串的所有排列。
对于此递归调用 return 集合中的每个排列，执行以下操作：
在这个排列中选择每个可能的索引，我们可以在其中插入一个字符，即 0 到较短字符串的长度（包括在内）：
- 在此排列中，在给定的索引处：插入被排除的字符，从而构造一个包含现在所有字符的排列。
因此第 3 步需要两个嵌套循环：一个用于获取较短字符串的每个排列，另一个用于 select 一个索引，在该索引处将被排除的字符插入到该排列中。
示例：
输入：
"abcd"
在第 2 步中，我们查看较短的字符串“abc”，并相信该函数会为其生成正确的结果（归纳推理），即集合：
{ "abc", "acb", "bac", "bca", "cab", "cba" }
现在我们进入第 3 步。外层循环遍历这个集合。内部循环选择 0 到 3（含）之间的索引。所以让我们把它放在 table:
shorter permutation
index at which to insert "d"
resulting permutation
"abc"
0
"dabc"
"abc"
1
"adbc"
"abc"
2
"abdc"
"abc"
3
"abcd"
"acb"
0
"dacb"
"acb"
1
"adcb"
"acb"
2
"acdb"
"acb"
3
"acbd"
"bac"
0
"dbac"
"bac"
1
"bdac"
"bac"
2
"badc"
"bac"
3
"bacd"
"bca"
0
"dbca"
"bca"
1
"bdca"
"bca"
2
"bcda"
"bca"
3
"bcad"
"cab"
0
"dcab"
"cab"
1
"cdab"
"cab"
2
"cadb"
"cab"
3
"cabd"
"cba"
0
"dcba"
"cba"
1
"cdba"
"cba"
2
"cbda"
"cba"
3
"cbad"
然后 return编辑此结果集。
希望这能说明问题。
你能帮我理解下面的代码片段吗？该注释说它正在通过回溯进行字符串排列，但我就是不明白。我不明白嵌套的 for 循环在做什么。我试着用“猫”来跟随代码。那么排列集没有吗？
public static Set<String> getPermutations(String inputString) {
if(inputString.length() <= 1) {
return new HashSet<>(Collections.singletonList(inputString));
}
String allCharsExceptLast = inputString.substring(0, inputString.length()-1);
char lastChar = inputString.charAt(inputString.length()-1);
Set<String> permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);
Set<String> permutations = new HashSet<>();
for(String permutationOfAllCharsExceptLast: permutationsOfAllCharsExceptLast) {
for(int position = 0; position <= allCharsExceptLast.length(); position++) {
String permutation = permutationOfAllCharsExceptLast.substring(0, position) + lastChar +
permutationOfAllCharsExceptLast.substring(position);
permutations.add(permutation);
}
}
return permutations;
}
}
算法的工作原理如下：
基本情况：当字符串只包含一个字符时，return只包含一个字符串的集合：这是唯一可能的排列。
解决少一个字符的问题：获取缺少原始最后一个字符的较短字符串的所有排列。
对于此递归调用 return 集合中的每个排列，执行以下操作：
在这个排列中选择每个可能的索引，我们可以在其中插入一个字符，即 0 到较短字符串的长度（包括在内）：
- 在此排列中，在给定的索引处：插入被排除的字符，从而构造一个包含现在所有字符的排列。
因此第 3 步需要两个嵌套循环：一个用于获取较短字符串的每个排列，另一个用于 select 一个索引，在该索引处将被排除的字符插入到该排列中。
示例：
输入：
"abcd"
在第 2 步中，我们查看较短的字符串“abc”，并相信该函数会为其生成正确的结果（归纳推理），即集合：
{ "abc", "acb", "bac", "bca", "cab", "cba" }
现在我们进入第 3 步。外层循环遍历这个集合。内部循环选择 0 到 3（含）之间的索引。所以让我们把它放在 table:
| shorter permutation | index at which to insert "d" | resulting permutation |
|---|---|---|
| "abc" | 0 | "dabc" |
| "abc" | 1 | "adbc" |
| "abc" | 2 | "abdc" |
| "abc" | 3 | "abcd" |
| "acb" | 0 | "dacb" |
| "acb" | 1 | "adcb" |
| "acb" | 2 | "acdb" |
| "acb" | 3 | "acbd" |
| "bac" | 0 | "dbac" |
| "bac" | 1 | "bdac" |
| "bac" | 2 | "badc" |
| "bac" | 3 | "bacd" |
| "bca" | 0 | "dbca" |
| "bca" | 1 | "bdca" |
| "bca" | 2 | "bcda" |
| "bca" | 3 | "bcad" |
| "cab" | 0 | "dcab" |
| "cab" | 1 | "cdab" |
| "cab" | 2 | "cadb" |
| "cab" | 3 | "cabd" |
| "cba" | 0 | "dcba" |
| "cba" | 1 | "cdba" |
| "cba" | 2 | "cbda" |
| "cba" | 3 | "cbad" |
然后 return编辑此结果集。
希望这能说明问题。