CODEWITHSUNDEEP
javaalgorithmdata-structuresbacktracking
adssdfd
adssdfd

Reputation: 3

Backtracking with recursion. Why is the code working

Could you please help me understanding the below code snippet. the note says it's doing a string permutation by back tracking but I just don't get it. I don't get what the nested for loops are doing. I tried to follow the code with "Cat". Doesn't permutation set have then?

public static Set<String> getPermutations(String inputString) {
        if(inputString.length() <= 1) {
            return new HashSet<>(Collections.singletonList(inputString));
        }
        String allCharsExceptLast = inputString.substring(0, inputString.length()-1);
        char lastChar = inputString.charAt(inputString.length()-1);

        Set<String> permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);

        Set<String> permutations = new HashSet<>();
        for(String permutationOfAllCharsExceptLast: permutationsOfAllCharsExceptLast) {
            for(int position = 0; position <= allCharsExceptLast.length(); position++) {
                String permutation = permutationOfAllCharsExceptLast.substring(0, position) + lastChar +
                        permutationOfAllCharsExceptLast.substring(position);
                permutations.add(permutation);
            }
        }

        return permutations;
    }

}

Upvotes: 0

Views: 99

Answers (1)

trincot
trincot

Reputation: 350345

The algorithm works as follows:

  1. The base case: when the string consists of just one character, then return a set with just that one string: it is the only possible permutation.

  2. Solve the problem for one character less: get all the permutations of the shorter string that lacks the original last character.

  3. For each permutation in the set that is returned by this recursive call, do the following:

    • Choose every possible index in this this permutation at which we can insert a character, i.e. 0 to the length of the shorter string (included):

      • In this permutation, at the given index: insert the excluded character, thereby constructing a permutation that has all the characters now.

So step 3 needs two nested loops: one to get each permutation of the shorter string, and another to select an index at which the excluded character is to be inserted into that permutation.

Example:

Input:

"abcd"

In step 2 we look at the shorter string "abc", and trust the function to produce the correct result for it (inductive reasoning), which is the set:

{ "abc", "acb", "bac", "bca", "cab", "cba" }

Now we get to step 3. The outer loop iterates over this set. The inner loop chooses an index between 0 and 3 (included). So let's put that in a table:

shorter permutation index at which to insert "d" resulting permutation
"abc" 0 "dabc"
"abc" 1 "adbc"
"abc" 2 "abdc"
"abc" 3 "abcd"
"acb" 0 "dacb"
"acb" 1 "adcb"
"acb" 2 "acdb"
"acb" 3 "acbd"
"bac" 0 "dbac"
"bac" 1 "bdac"
"bac" 2 "badc"
"bac" 3 "bacd"
"bca" 0 "dbca"
"bca" 1 "bdca"
"bca" 2 "bcda"
"bca" 3 "bcad"
"cab" 0 "dcab"
"cab" 1 "cdab"
"cab" 2 "cadb"
"cab" 3 "cabd"
"cba" 0 "dcba"
"cba" 1 "cdba"
"cba" 2 "cbda"
"cba" 3 "cbad"

This resulting set is then returned.

Hope this clarifies it.

Upvotes: 2

Related Questions