java如何使用尾部递归和/或流来查找字符串的所有排列，而不会耗尽长字符串的内存

Question

我编写了以下代码，用于返回字符串的所有排列的数组。对于长字符串，这会导致问题吗？例如，我怀疑Java将无法使用尾部递归，因为递归调用不是函数的最后一次调用，这可能会导致堆栈溢出。此外，我的解决方案收集所有可能的排列，并在单个数组中返回它们。由于排列的数量随着字符串的长度而爆炸，因此对于长字符串，数组将无法放入内存中。这可以补救吗？也许用流来代替

public static String[] perms(String str) {
        String[] permutations = new String[factorial(str.length())];
        int permIdx = 0;

        if (str.length() == 1) {
            return new String[]{str};
        }

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String restOfString = str.substring(0, i) + str.substring(i + 1);
            String[] permutationsOfRestString = perms(restOfString);
            for (String permutation : permutationsOfRestString) {
                permutations[permIdx++] = ch + permutation;
            }
        }

        return permutations;
    }

    public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        } else {
            return n * factorial(--n);
        }
    }

Answer 1

此解决方案有助于根除java.lang.OutOfMemoryError: GC

public static List<String> generatepermutations(String str) {
    List<Character> chars = new ArrayList<>();
    for (char ch : str.toCharArray()) {
        chars.add(ch);
    }
    List<String> fl = new ArrayList<>();
    for (int i = 0; i < chars.size(); i++) {
        char ch = chars.get(i);
        List<Character> templist = new ArrayList<>();
        chars.stream().forEach(e -> templist.add(e));
        templist.remove(i);
        Collections.sort(templist);
        for (int j = 0; j < chars.size(); j++) {
            templist.add(j, ch);
            String t = templist.toString().replace("[", "").replace("]", "").replace(", ", "");
            fl.add(t);
            templist.remove(j);
        }
    }
    System.out.println(fl);
    return fl;
}

Answer 2

可以创建一个不必在内存中保存所有结果字符串的流解决方案，例如

public static Stream<String> perms(String str) {
    if(str.length() <= 1) return Stream.of(str);
    return IntStream.range(0, str.length()).boxed()
        .flatMap(ix -> perms(new StringBuilder(str).deleteCharAt(ix).toString())
            .map(s  -> str.charAt(ix) + s));
}

递归步骤已替换为flatMap步骤，该步骤将被延迟计算

当然，这取决于您链接到流的终端操作，以及这一优势是否实现。例如，当你把toArray()链接起来时，你就会回到原点。但是chaining.forEach(System.out::println)将打印排列，而不需要将所有排列都存储在内存中

---

作为一个小优化，如果我们放松方法以接受CharSequence实现作为输入（包括String），我们可以在中间步骤中省略toString操作，并直接传递StringBuilder。因此，我们在提高方法灵活性的同时，也提高了性能

public static Stream<String> perms(CharSequence str) {
    if(str.length() <= 1) return Stream.of(str.toString());
    return IntStream.range(0, str.length()).boxed()
        .flatMap(ix -> perms(new StringBuilder(str).deleteCharAt(ix))
            .map(s -> str.charAt(ix)+s));
}