CODEWITHSUNDEEP
javascriptrecursionrecursive-datastructures
shubham
shubham

Reputation: 101

How recursion works in case of permutations after the base case reached

When the base case is reached then for next combination call we re-swap how it is taking in to account the not visited or considered cases.

For example

 function dfs(i, nums, slate) {
    if (i === nums.length) {
        result.push(slate.slice());
        return; // Terminate the current branch of recursion
    }

    for (let j = i; j < nums.length; j++) {
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Swap elements
        dfs(i + 1, nums, slate.concat(nums[i])); // Recur with the next index
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Backtrack: Restore original state
    }
}

This code we are restoring to original after swapping, how it is taking next value or unvisited value or not considered value as we are not returning anything. Can anyone help me understand?

I want to understand the unwinding of calls from stack and how the next cases are considered. After base case reached and how it is working. Thanks

Upvotes: 0

Views: 86

Answers (1)

trincot
trincot

Reputation: 350771

The background for this algorithm is the following:

A permutation is formed by repeatedly selecting any available value from the input list to become the next value in the permutation we are building. In this process the number of available values shrinks until there are no more, and at the same time the number of selected values grows until we have a full permutation.

To get other permutations we need to make all possible selections at each index, so with backtracking we can undo the most recently made selection and select another value if possible. When all possibilities have been tried at that stage, we backtrack again to deal with the alternatives there,... etc.

A key insight is that this algorithm reserves the left side of the input array for the part that is selected, and the right side of the array to store the values that are still available for the remaining selections. The separation between these two subarrays is at index i. The left partition has size i, and the right partition starts at that index.

So let's say we have already selected a few values and we are at index i. The goal here is to choose a value from the right partition and place it at index i (it could even be the value that is already at that index, since that value also belongs to the right partition). And once we have selected it, we can declare that index to be part of the left partition. This we do by the recursive call with i + 1.

The swapping mechanism (when j > i) is used to achieve two things:

  1. To move the selected value from index j at index i, so that now it is selected and will become part of the left partition once i is incremented.
  2. To move the not-selected value that was at index i to another place in the right partition. Since at index j we now have room for it, it gets placed there.

When backtracking, it is important to restore the array to what it was before that swap was made, because at higher levels in the recursion tree (where i is smaller), there are loops ongoing that rely on this invariant: their j should not encounter a value it had already dealt with at an earlier index.

So we want to restore the array to what it was before that swap was made, and so we "unswap" these two values. We can be sure that these are the same two that got swapped before the recursive call was made, because with this unswap, each recursive call will guarantee that the array will be restored to what it was before the call was made.

This unswap is not yet the selection of a different value. That only happens in the next iteration of the j loop. This restoration only prepares the way for the next alternative selection to be made in the next iteration.

Without slate

The slate parameter of your implementation is not really needed. As the input array is used to store both partitions, the permutation will be represented in that array itself when you have reached the end of recursion, and you can just add a copy of that array into the result set.

Also, you can avoid accessing an "outside" result variable, by turning this function into a generator. It then becomes the responsibility of the caller to collect the generated permutations in an array -- if they wish to do so.

Finally, I would make i the second parameter, so that you can give it a default value of 0, and the initial caller only has to pass one argument -- the array of values to permute.

Here is how that looks:

function* dfs(nums, i=0) { // Rearranged parameters
    if (i === nums.length) {
        yield nums.slice(); // nums itself has the permutation!
        return;
    }

    for (let j = i; j < nums.length; j++) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        yield* dfs(nums, i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]]; // Backtrack: Restore original state
    }
}

// Example call
const result = [...dfs([1, 2, 3])];
console.log(result);

Upvotes: 0

Related Questions