How to use tail recursion and/or Streams to find all permutations of a string without running out of memory for long strings

Question

I've written the following code for returning an array of all permutations of a string. For long strings, will this lead to problems? I suspect for example that Java will not be able to use tail recursion, since the recursive call is not the last call of the function, which will possibly lead to stack overflow. Also, my solution collects all possible permutations and returns them in one single array. Since the number of permutations explodes with the length of the string, the array won't fit into memory for long strings. Can this be remedied somehow? Perhaps by using a Stream instead?

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);
        }
    }

The concept of [tag:java-stream] is not suitable for any kind of recursive operations. They are built for a collection processing. — Nikolas Charalambidis, Jun 18 '20 at 06:01
@Nikolas actually, this can be expressed with the Stream API without any kludges. — Holger, Jun 18 '20 at 08:35

Holger · Accepted Answer · 2020-06-18T08:41:46.867

It’s possible to create a Stream solution that doesn’t have to hold all result strings in memory, e.g.

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));
}

The recursion step has been replaced with a flatMap step which will be evaluated lazily.

Of course, it depends on the terminal operation you chain to the stream, whether this advantage materializes. E.g. when you chain toArray(), you’ll be back at square one. But chaining .forEach(System.out::println) will print the permutations without the need to have all of them in memory.

As a small optimization, if we relax the method to accept CharSequence implementations as input (which includes String), we can elide the toString operation in the intermediate step and pass the StringBuilder directly. So we raise the flexibility of the method and the performance at the same time.

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));
}

score 0 · Answer 2 · answered Jul 23 '20 at 19:42

This solution could help eradicate 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;
}

How to use tail recursion and/or Streams to find all permutations of a string without running out of memory for long strings

2 Answers2