在 Java 中使用递归的字符串排列
String permutations using recursion in Java
我遇到了 THIS post，它非常努力地解释打印所有字符串的递归解决方案。
public class Main {
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i),
str.substring(0, i) + str.substring(i + 1));
}
}
public static void main(String[] args) {
permutation("", "ABCD");
}
}
但是当我们开始从堆栈中弹出时，我仍然无法得到这个部分。例如，递归一直进行到 permutation("ABCD","")，其中满足基本情况并打印 ABCD。但是现在发生了什么？我们从函数调用堆栈中弹出 permutation("ABC","D")。我们用这个做什么等等？
有人可以帮忙解释一下吗？
此外，我需要一些关于此时间复杂度的指示。不像完整的计算，而是一些提示。
更简单的示例：permutation("", "ABC")，将空字符串表示为 *:
* ABC + A BC + AB C - ABC *
| |
| ` AC B - ACB *
|
+ B AC + BA C - BAC *
| |
| ` BC A - BCA *
|
` C AB + CA B - CAB *
|
` CB A - CBA *
请注意，这看起来像是一棵侧放的树。确实，它叫做一棵树。当我们启动时，会进入("A", "BC")状态；我们继续调用 ("AB", "C")，最后调用 ("ABC", "")。在这里我们打印我们的输出。然后我们记得我们还有未完成的事情，我们return来一个循环，但是上一层的循环只有一个循环。所以我们也在那里完成了，return 回到了 ("A", "BC") 水平； "BC" 中有两个元素，我们只完成了 "B"，所以现在轮到 "C"：我们调用 ("AC", "B")，然后调用 ("ACB", "") ].现在 ("A", "BC") 下的所有循环都完成了......但是等等，还有工作要做！因为 ("", "ABC") 还有两个字母要处理。就这样，一个分支一个分支，我们通常称之为 "depth-first search".
每一层都有一个循环。循环缩小了（我们在左边的粗分支中迭代了 3 次，然后在下一级迭代了 2 次，然后只有一次）但仍然存在循环。因此，我们总共进行了 n * (n - 1) * (n - 2) * ... * 2 * 1 次迭代。 O(N!)?
作为一种递归，可以使用Stream.reduce方法。首先为每个 character-position 准备一个 list 可能的字符组合，然后连续 reduce通过对列表元素对求和，将这些列表流化为单个列表。
作为列表元素，可以使用Map<Integer,String>，其中key-字符在字符串中的位置，value - 字符本身，并对这些映射的内容求和，不包括那些已经存在的 keys。
你会得到一个字符排列列表。
比如你有一个四字串</code>，那么你要经过<em>归约</em>三个步骤，连续累加结果：</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>str1 + str2 = sum1</th>
<th>sum1 + str3 = sum2</th>
<th>sum2 + str4 = total</th>
</tr>
</thead>
<tbody>
<tr>
<td><pre> + = <br> + = <br> + = </pre></td>
<td><pre> + = <br> + = <br> + = <br> + = <br> + = <br> + = </pre></td>
<td><pre> + = <br> + = <br> + = <br> + = <br> + = <br> + = </pre></td>
</tr>
</tbody>
</table>
</div>
<p><code>15 每个 4 字符的总和是 60 总和，导致 4! = 24 排列。
// original string
String str = "";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
// contents of the array
System.out.println(Arrays.toString(codePoints));
//[120276, 120277, 120278, 120279]
// list of permutations of characters
List<Map<Integer, String>> permutations = IntStream.range(0, codePoints.length)
// Stream<List<Map<Integer,String>>>
.mapToObj(i -> IntStream.range(0, codePoints.length)
// represent each character as Map<Integer,String>
.mapToObj(j -> Map.of(j, Character.toString(codePoints[j])))
// collect a list of maps
.collect(Collectors.toList()))
// intermediate output
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
.peek(System.out::println)
// reduce a stream of lists to a single list
.reduce((list1, list2) -> list1.stream()
// summation of pairs of maps from two lists
.flatMap(map1 -> list2.stream()
// filter out those keys that are already present
.filter(map2 -> map2.keySet().stream()
.noneMatch(map1::containsKey))
// join entries of two maps
.map(map2 -> new LinkedHashMap<Integer, String>() {{
putAll(map1);
putAll(map2);
}}))
// collect into a single list
.collect(Collectors.toList()))
// List<Map<Integer,String>>
.orElse(List.of(Map.of(0, str)));
// number of permutations
System.out.println(permutations.size()); // 24
// number of rows (factorial of string length - 1)
int rows = IntStream.range(1, codePoints.length)
.reduce((a, b) -> a * b).orElse(1);
// column-wise output
IntStream.range(0, rows)
.mapToObj(i -> IntStream.range(0, permutations.size())
.filter(j -> j % rows == i)
.mapToObj(permutations::get)
.map(map -> map.toString().replace(" ", ""))
.collect(Collectors.joining(" ")))
.forEach(System.out::println);
//{0=,1=,2=,3=} {1=,0=,2=,3=} {2=,0=,1=,3=} {3=,0=,1=,2=}
//{0=,1=,3=,2=} {1=,0=,3=,2=} {2=,0=,3=,1=} {3=,0=,2=,1=}
//{0=,2=,1=,3=} {1=,2=,0=,3=} {2=,1=,0=,3=} {3=,1=,0=,2=}
//{0=,2=,3=,1=} {1=,2=,3=,0=} {2=,1=,3=,0=} {3=,1=,2=,0=}
//{0=,3=,1=,2=} {1=,3=,0=,2=} {2=,3=,0=,1=} {3=,2=,0=,1=}
//{0=,3=,2=,1=} {1=,3=,2=,0=} {2=,3=,1=,0=} {3=,2=,1=,0=}
另请参阅：
您可以使用 map 和 reduce 方法生成字符串排列数组。
此解决方案假定原始字符串不包含重复字符，否则应使用 排列映射 Map<Integer,String> 而不是 排列数组 String[].
reduce 方法采用一对 排列数组 并将它们的元素 成对 相加，累加结果。例如5个字符的字符串</code>:</p>的四步归约
<pre><code>0 [, , , , ]
1 [, , , , ]
---
sum1: [, , , , ...]
2 [, , , , ]
---
sum2: [, , , ...]
3 [, , , , ]
---
sum3: [, , ...]
4 [, , , , ]
---
total: [, , ...]
// original string
String str = "";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
String[] permutations = IntStream.range(0, codePoints.length)
// intermediate output, character-position
.peek(i -> System.out.print(i + " "))
// prepare an array of possible permutations for each character-position
.mapToObj(i -> Arrays.stream(codePoints).mapToObj(Character::toString)
// array of characters as strings
.toArray(String[]::new))
// intermediate output, array of possible permutations
.peek(arr -> System.out.println(Arrays.deepToString(arr)))
// reduce a stream of arrays to a single array
.reduce((arr1, arr2) -> Arrays.stream(arr1)
// summation of pairs of strings from two arrays
.flatMap(str1 -> Arrays.stream(arr2)
// filter out those characters that are already present
.filter(str2 -> !str1.contains(str2))
// concatenate two strings
.map(str2 -> str1 + str2))
// collect into a single array
.toArray(String[]::new))
// otherwise an empty array
.orElse(new String[0]);
// final output
System.out.println("Number of permutations: " + permutations.length);
// number of rows
int rows = permutations.length / 10;
// permutations by columns
IntStream.range(0, rows).forEach(i -> System.out.println(
IntStream.range(0, permutations.length)
.filter(j -> j % rows == i)
.mapToObj(j -> permutations[j])
.collect(Collectors.joining(" "))));
中间输出，每个字符位置的可能排列数组：
0 [, , , , ]
1 [, , , , ]
2 [, , , , ]
3 [, , , , ]
4 [, , , , ]
最终输出，按列排列：
Number of permutations: 120
我遇到了 THIS post，它非常努力地解释打印所有字符串的递归解决方案。
public class Main {
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i),
str.substring(0, i) + str.substring(i + 1));
}
}
public static void main(String[] args) {
permutation("", "ABCD");
}
}
但是当我们开始从堆栈中弹出时，我仍然无法得到这个部分。例如，递归一直进行到 permutation("ABCD","")，其中满足基本情况并打印 ABCD。但是现在发生了什么？我们从函数调用堆栈中弹出 permutation("ABC","D")。我们用这个做什么等等？
有人可以帮忙解释一下吗？
此外，我需要一些关于此时间复杂度的指示。不像完整的计算，而是一些提示。
更简单的示例：permutation("", "ABC")，将空字符串表示为 *:
* ABC + A BC + AB C - ABC *
| |
| ` AC B - ACB *
|
+ B AC + BA C - BAC *
| |
| ` BC A - BCA *
|
` C AB + CA B - CAB *
|
` CB A - CBA *
请注意，这看起来像是一棵侧放的树。确实，它叫做一棵树。当我们启动时，会进入("A", "BC")状态；我们继续调用 ("AB", "C")，最后调用 ("ABC", "")。在这里我们打印我们的输出。然后我们记得我们还有未完成的事情，我们return来一个循环，但是上一层的循环只有一个循环。所以我们也在那里完成了，return 回到了 ("A", "BC") 水平； "BC" 中有两个元素，我们只完成了 "B"，所以现在轮到 "C"：我们调用 ("AC", "B")，然后调用 ("ACB", "") ].现在 ("A", "BC") 下的所有循环都完成了......但是等等，还有工作要做！因为 ("", "ABC") 还有两个字母要处理。就这样，一个分支一个分支，我们通常称之为 "depth-first search".
每一层都有一个循环。循环缩小了（我们在左边的粗分支中迭代了 3 次，然后在下一级迭代了 2 次，然后只有一次）但仍然存在循环。因此，我们总共进行了 n * (n - 1) * (n - 2) * ... * 2 * 1 次迭代。 O(N!)?
作为一种递归，可以使用Stream.reduce方法。首先为每个 character-position 准备一个 list 可能的字符组合，然后连续 reduce通过对列表元素对求和，将这些列表流化为单个列表。
作为列表元素，可以使用Map<Integer,String>，其中key-字符在字符串中的位置，value - 字符本身，并对这些映射的内容求和，不包括那些已经存在的 keys。
你会得到一个字符排列列表。
比如你有一个四字串</code>，那么你要经过<em>归约</em>三个步骤，连续累加结果：</p>
<div class="s-table-container">
<table class="s-table">
<thead>
<tr>
<th>str1 + str2 = sum1</th>
<th>sum1 + str3 = sum2</th>
<th>sum2 + str4 = total</th>
</tr>
</thead>
<tbody>
<tr>
<td><pre> + = <br> + = <br> + = </pre></td>
<td><pre> + = <br> + = <br> + = <br> + = <br> + = <br> + = </pre></td>
<td><pre> + = <br> + = <br> + = <br> + = <br> + = <br> + = </pre></td>
</tr>
</tbody>
</table>
</div>
<p><code>15 每个 4 字符的总和是 60 总和，导致 4! = 24 排列。
// original string
String str = "";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
// contents of the array
System.out.println(Arrays.toString(codePoints));
//[120276, 120277, 120278, 120279]
// list of permutations of characters
List<Map<Integer, String>> permutations = IntStream.range(0, codePoints.length)
// Stream<List<Map<Integer,String>>>
.mapToObj(i -> IntStream.range(0, codePoints.length)
// represent each character as Map<Integer,String>
.mapToObj(j -> Map.of(j, Character.toString(codePoints[j])))
// collect a list of maps
.collect(Collectors.toList()))
// intermediate output
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
//[{0=}, {1=}, {2=}, {3=}]
.peek(System.out::println)
// reduce a stream of lists to a single list
.reduce((list1, list2) -> list1.stream()
// summation of pairs of maps from two lists
.flatMap(map1 -> list2.stream()
// filter out those keys that are already present
.filter(map2 -> map2.keySet().stream()
.noneMatch(map1::containsKey))
// join entries of two maps
.map(map2 -> new LinkedHashMap<Integer, String>() {{
putAll(map1);
putAll(map2);
}}))
// collect into a single list
.collect(Collectors.toList()))
// List<Map<Integer,String>>
.orElse(List.of(Map.of(0, str)));
// number of permutations
System.out.println(permutations.size()); // 24
// number of rows (factorial of string length - 1)
int rows = IntStream.range(1, codePoints.length)
.reduce((a, b) -> a * b).orElse(1);
// column-wise output
IntStream.range(0, rows)
.mapToObj(i -> IntStream.range(0, permutations.size())
.filter(j -> j % rows == i)
.mapToObj(permutations::get)
.map(map -> map.toString().replace(" ", ""))
.collect(Collectors.joining(" ")))
.forEach(System.out::println);
//{0=,1=,2=,3=} {1=,0=,2=,3=} {2=,0=,1=,3=} {3=,0=,1=,2=}
//{0=,1=,3=,2=} {1=,0=,3=,2=} {2=,0=,3=,1=} {3=,0=,2=,1=}
//{0=,2=,1=,3=} {1=,2=,0=,3=} {2=,1=,0=,3=} {3=,1=,0=,2=}
//{0=,2=,3=,1=} {1=,2=,3=,0=} {2=,1=,3=,0=} {3=,1=,2=,0=}
//{0=,3=,1=,2=} {1=,3=,0=,2=} {2=,3=,0=,1=} {3=,2=,0=,1=}
//{0=,3=,2=,1=} {1=,3=,2=,0=} {2=,3=,1=,0=} {3=,2=,1=,0=}
另请参阅：
您可以使用 map 和 reduce 方法生成字符串排列数组。
此解决方案假定原始字符串不包含重复字符，否则应使用 排列映射 Map<Integer,String> 而不是 排列数组 String[].
reduce 方法采用一对 排列数组 并将它们的元素 成对 相加，累加结果。例如5个字符的字符串</code>:</p>的四步归约
<pre><code>0 [, , , , ]
1 [, , , , ]
---
sum1: [, , , , ...]
2 [, , , , ]
---
sum2: [, , , ...]
3 [, , , , ]
---
sum3: [, , ...]
4 [, , , , ]
---
total: [, , ...]
// original string
String str = "";
// array of characters of the string
int[] codePoints = str.codePoints().toArray();
String[] permutations = IntStream.range(0, codePoints.length)
// intermediate output, character-position
.peek(i -> System.out.print(i + " "))
// prepare an array of possible permutations for each character-position
.mapToObj(i -> Arrays.stream(codePoints).mapToObj(Character::toString)
// array of characters as strings
.toArray(String[]::new))
// intermediate output, array of possible permutations
.peek(arr -> System.out.println(Arrays.deepToString(arr)))
// reduce a stream of arrays to a single array
.reduce((arr1, arr2) -> Arrays.stream(arr1)
// summation of pairs of strings from two arrays
.flatMap(str1 -> Arrays.stream(arr2)
// filter out those characters that are already present
.filter(str2 -> !str1.contains(str2))
// concatenate two strings
.map(str2 -> str1 + str2))
// collect into a single array
.toArray(String[]::new))
// otherwise an empty array
.orElse(new String[0]);
// final output
System.out.println("Number of permutations: " + permutations.length);
// number of rows
int rows = permutations.length / 10;
// permutations by columns
IntStream.range(0, rows).forEach(i -> System.out.println(
IntStream.range(0, permutations.length)
.filter(j -> j % rows == i)
.mapToObj(j -> permutations[j])
.collect(Collectors.joining(" "))));
中间输出，每个字符位置的可能排列数组：
0 [, , , , ]
1 [, , , , ]
2 [, , , , ]
3 [, , , , ]
4 [, , , , ]
最终输出，按列排列：
Number of permutations: 120