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.

Amadan · Accepted Answer · 2015-01-09 08:42:18Z

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!)?

score 1 · Accepted Answer · 2021-04-17 12:19:25Z

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?}

score 1 · Accepted Answer · 2021-04-25 13:17:29Z

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
𝖠𝖡𝖢𝖣𝖤 𝖠𝖣𝖡𝖢𝖤 𝖡𝖠𝖢𝖣𝖤 𝖡𝖣𝖠𝖢𝖤 𝖢𝖠𝖡𝖣𝖤 𝖢𝖣𝖠𝖡𝖤 𝖣𝖠𝖡𝖢𝖤 𝖣𝖢𝖠𝖡𝖤 𝖤𝖠𝖡𝖢𝖣 𝖤𝖢𝖠𝖡𝖣
𝖠𝖡𝖢𝖤𝖣 𝖠𝖣𝖡𝖤𝖢 𝖡𝖠𝖢𝖤𝖣 𝖡𝖣𝖠𝖤𝖢 𝖢𝖠𝖡𝖤𝖣 𝖢𝖣𝖠𝖤𝖡 𝖣𝖠𝖡𝖤𝖢 𝖣𝖢𝖠𝖤𝖡 𝖤𝖠𝖡𝖣𝖢 𝖤𝖢𝖠𝖣𝖡
𝖠𝖡𝖣𝖢𝖤 𝖠𝖣𝖢𝖡𝖤 𝖡𝖠𝖣𝖢𝖤 𝖡𝖣𝖢𝖠𝖤 𝖢𝖠𝖣𝖡𝖤 𝖢𝖣𝖡𝖠𝖤 𝖣𝖠𝖢𝖡𝖤 𝖣𝖢𝖡𝖠𝖤 𝖤𝖠𝖢𝖡𝖣 𝖤𝖢𝖡𝖠𝖣
𝖠𝖡𝖣𝖤𝖢 𝖠𝖣𝖢𝖤𝖡 𝖡𝖠𝖣𝖤𝖢 𝖡𝖣𝖢𝖤𝖠 𝖢𝖠𝖣𝖤𝖡 𝖢𝖣𝖡𝖤𝖠 𝖣𝖠𝖢𝖤𝖡 𝖣𝖢𝖡𝖤𝖠 𝖤𝖠𝖢𝖣𝖡 𝖤𝖢𝖡𝖣𝖠
𝖠𝖡𝖤𝖢𝖣 𝖠𝖣𝖤𝖡𝖢 𝖡𝖠𝖤𝖢𝖣 𝖡𝖣𝖤𝖠𝖢 𝖢𝖠𝖤𝖡𝖣 𝖢𝖣𝖤𝖠𝖡 𝖣𝖠𝖤𝖡𝖢 𝖣𝖢𝖤𝖠𝖡 𝖤𝖠𝖣𝖡𝖢 𝖤𝖢𝖣𝖠𝖡
𝖠𝖡𝖤𝖣𝖢 𝖠𝖣𝖤𝖢𝖡 𝖡𝖠𝖤𝖣𝖢 𝖡𝖣𝖤𝖢𝖠 𝖢𝖠𝖤𝖣𝖡 𝖢𝖣𝖤𝖡𝖠 𝖣𝖠𝖤𝖢𝖡 𝖣𝖢𝖤𝖡𝖠 𝖤𝖠𝖣𝖢𝖡 𝖤𝖢𝖣𝖡𝖠
𝖠𝖢𝖡𝖣𝖤 𝖠𝖤𝖡𝖢𝖣 𝖡𝖢𝖠𝖣𝖤 𝖡𝖤𝖠𝖢𝖣 𝖢𝖡𝖠𝖣𝖤 𝖢𝖤𝖠𝖡𝖣 𝖣𝖡𝖠𝖢𝖤 𝖣𝖤𝖠𝖡𝖢 𝖤𝖡𝖠𝖢𝖣 𝖤𝖣𝖠𝖡𝖢
𝖠𝖢𝖡𝖤𝖣 𝖠𝖤𝖡𝖣𝖢 𝖡𝖢𝖠𝖤𝖣 𝖡𝖤𝖠𝖣𝖢 𝖢𝖡𝖠𝖤𝖣 𝖢𝖤𝖠𝖣𝖡 𝖣𝖡𝖠𝖤𝖢 𝖣𝖤𝖠𝖢𝖡 𝖤𝖡𝖠𝖣𝖢 𝖤𝖣𝖠𝖢𝖡
𝖠𝖢𝖣𝖡𝖤 𝖠𝖤𝖢𝖡𝖣 𝖡𝖢𝖣𝖠𝖤 𝖡𝖤𝖢𝖠𝖣 𝖢𝖡𝖣𝖠𝖤 𝖢𝖤𝖡𝖠𝖣 𝖣𝖡𝖢𝖠𝖤 𝖣𝖤𝖡𝖠𝖢 𝖤𝖡𝖢𝖠𝖣 𝖤𝖣𝖡𝖠𝖢
𝖠𝖢𝖣𝖤𝖡 𝖠𝖤𝖢𝖣𝖡 𝖡𝖢𝖣𝖤𝖠 𝖡𝖤𝖢𝖣𝖠 𝖢𝖡𝖣𝖤𝖠 𝖢𝖤𝖡𝖣𝖠 𝖣𝖡𝖢𝖤𝖠 𝖣𝖤𝖡𝖢𝖠 𝖤𝖡𝖢𝖣𝖠 𝖤𝖣𝖡𝖢𝖠
𝖠𝖢𝖤𝖡𝖣 𝖠𝖤𝖣𝖡𝖢 𝖡𝖢𝖤𝖠𝖣 𝖡𝖤𝖣𝖠𝖢 𝖢𝖡𝖤𝖠𝖣 𝖢𝖤𝖣𝖠𝖡 𝖣𝖡𝖤𝖠𝖢 𝖣𝖤𝖢𝖠𝖡 𝖤𝖡𝖣𝖠𝖢 𝖤𝖣𝖢𝖠𝖡
𝖠𝖢𝖤𝖣𝖡 𝖠𝖤𝖣𝖢𝖡 𝖡𝖢𝖤𝖣𝖠 𝖡𝖤𝖣𝖢𝖠 𝖢𝖡𝖤𝖣𝖠 𝖢𝖤𝖣𝖡𝖠 𝖣𝖡𝖤𝖢𝖠 𝖣𝖤𝖢𝖡𝖠 𝖤𝖡𝖣𝖢𝖠 𝖤𝖣𝖢𝖡𝖠

Collectives™ on Stack Overflow

String permutations using recursion in Java

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related