String permutations using recursion in Java

Question

I came across THIS post which tried very hard to explain the recursive solution to print all string.

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

But still I am not able to get the part when we start popping off the stack. For example, recursion goes all the way till permutation("ABCD",""), where base case meets and it prints ABCD. But what happens now? We pop off permutation("ABC","D") from function call stack. What we do with this and so on?

Can someone please help explain a bit?

Also, I need some pointers on the time complexity of this. Not like complete calculation but some hints.

Answer 1

Easier example: permutation("", "ABC"), representing empty string as *:

* 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 *

Note that this looks like a tree laid on its side. Indeed, it called a tree. When we start, we will enter ("A", "BC") state; we proceed to call ("AB", "C"), and finally ("ABC", ""). Here we print our output. Then we remember we have unfinished business, we return to a loop, but the loop in the previous level only had one cycle. So we're done there as well, and return back to ("A", "BC") level; there are two elements in "BC" and we've only done the "B", so it's now "C"'s turn: we call ("AC", "B"), which then calls ("ACB", ""). Now all the loops under ("A", "BC") are done... But wait, still work to do! Because ("", "ABC") still has two more letters to process. And so it goes, branch by branch, in what we usually call "depth-first search".

In each level is a loop. The loop shrinks (we iterate 3 times in the thick branch at the left, then 2 in the next level, then only one) but still there is a loop. So in total, we do n * (n - 1) * (n - 2) * ... * 2 * 1 iterations. O(N!)?

Answer 2

As a kind of recursion, you can use Stream.reduce method. First prepare a list of possible combinations of characters for each character-position, and then consecutively reduce the stream of these lists to a single list, by summing the pairs of list elements.

As a list element, you can use Map<Integer,String>, where key - the position of the character in the string, value - the character itself, and summ the contents of these maps, excluding those keys that are already present.

And you get a list of permutations of characters.

For example, if you have a four-character string , then you have to pass through three steps of reduction, consecutively accumulating the results:

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

15 sums for each of the 4 characters are 60 sums, resulting in 4! = 24 permutations.

Try it online!

// 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=}

---

^{See also: How do you check if a word has an anagram that is a palindrome?}

Answer 3

You can generate an array of permutations of the string using map and reduce methods.

This solution assumes that the original string does not contain duplicate characters, otherwise the permutation maps Map<Integer,String> should be used instead of the permutation arrays String[].

The reduce method takes a pair of permutation arrays and sums their elements in pairs, accumulating the results. For example, four steps of reduction for a five-character string :

0 [, , , , ]
1 [, , , , ]
---
sum1: [, , , , ...]
2 [, , , , ]
---
sum2: [, , , ...]
3 [, , , , ]
---
sum3: [, , ...]
4 [, , , , ]
---
total: [, , ...]

Try it online!

// 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(" "))));

Intermediate output, arrays of possible permutations for each character-position:

0 [, , , , ]
1 [, , , , ]
2 [, , , , ]
3 [, , , , ]
4 [, , , , ]

Final output, permutations by columns:

Number of permutations: 120