使用递归在Java中实现字符串的排列

Question

我发现了这篇文章，它非常努力地解释了递归解决方案来打印所有字符串。

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")，那么我们该怎么做等等？

请问有人能够帮忙解释一下吗？

此外，我需要一些关于时间复杂度的指示。不是完整的计算，而是一些提示。

- Walt

Answer 1

更简单的例子：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", "")。在这里我们打印输出。然后我们记得我们还有未完成的任务，我们返回到一个循环，但是前一个级别的循环只有一个周期。所以我们也完成了那里的工作，并返回到 ("A", "BC") 级别；在 "BC" 中有两个元素，我们只处理了 "B"，所以现在轮到了 "C"：我们调用 ("AC", "B")，然后调用 ("ACB", "")。现在所有在 ("A", "BC") 下面的循环都完成了... 但等等，还有工作要做！因为 ("", "ABC") 还有两个字母要处理。于是它就像分支一样，以我们通常所说的“深度优先搜索”的方式展开。

在每个级别中都有一个循环。循环收缩了（我们在左边的粗分支中迭代了 3 次，然后在下一个级别中迭代了 2 次，然后只有一次），但仍然存在着一个循环。所以总共，我们要迭代 n * (n - 1) * (n - 2) * ... * 2 * 1 次。是 O(N!) 吗？

- Amadan

Answer 2

作为一种递归，您可以使用Stream.reduce方法。首先准备每个字符位置的可能字符组合的列表，然后通过对这些列表的流进行连续的reduce，通过对列表元素对求和，将其缩减为单个列表。

作为列表元素，您可以使用Map<Integer,String>，其中key是字符串中字符的位置，value是字符本身，并对这些映射的内容进行求和，排除已经存在的keys。

然后您会得到一个字符排列的列表。

例如，如果您有一个四个字符的字符串，那么您必须通过三个reduction步骤，连续累积结果：

str1 + str2 = sum1	sum1 + str3 = sum2	sum2 + str4 = total
+ = + = + =	+ = + = + = + = + = + =	+ = + = + = + = + = + =

15个和为60的数，对于每个字符有4个和，共有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=}

---

^{另请参阅：如何检查一个单词是否有回文的变位词？}

- user15613375

Answer 3

你可以使用map和reduce方法生成字符串的排列数组。

这个解决方案假设原始字符串不包含重复字符，否则应该使用排列映射Map<Integer,String>而不是排列数组String[]。 reduce方法接受一对排列数组并将它们的元素逐对相加，累积结果。例如，对于一个五个字符的字符串，需要进行四步缩减：。

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
         
         
         
         
         
         
         
         
         
         
         
         

- user15675591