Permutation of String Problem

#1

I didn’t understan the recursion tree .how the program ctrl is going onwards?
https://jamboard.google.com/d/1E6SOCTdykC1S7y2p_RCC04xF1JVi7ivOVC0ANM_oris/viewer?f=0

#2

how to thing recursively when we have recursively inside the loop:
I am always confused when when we hit the base case and return the value and again we make the another call . For Example :

[quote=“Vikaspal, post:1, topic:37939, full:true”]
problem

so how to think properly ?
I

#3

Hi @Vikaspal


try going through this article once and dry running the code on N=3 having S=“ABC” or N=“4” and S=“ABCD”.
If u r still not able to understand anything, or have any confusion, feel free to post ur doubts here.
Hope dis helps.

#4

@Yash_N
I am try to dry the run without the backtracking but i stuck in the some steps recursion when the base case return the value : I will share a photo hope this you explain you where i am stuck. I am just trying to find out first what are the problem arise when we don’t use the backtracking.

permute
permute1027×556 87.5 KB

#5

Also how to handle those case when have the repeated elments

#6

@Vikaspal,
suppose u have string=‘abc’.
in the pic u have shared, u will reach at a point when i==3 and j==3 i.e i ==n.
so u will and cout the permuted value using
if (l == r)
cout<<a<<endl;
now u back track to the step when i=2 and j=2 and swap i=2 and j=3. now abc will become->acb.
now u again call the function and have i==3 and j==3 i.e i==n.
so u will cout acb.
now u back track to the step when i=2 and j=3 .Now since no more cases can be assumed in this case, we backtrack again to i=1, j=1. now swap i=1 j=2. string now becomes ‘bac’.
now call function on i=2,j=2 and then on i=3 and j=3. and cout using base case bac.
now backtrack to i=2,j=2 and swap i=2,j=3 and cout bca and so on.

hope dis helps.
if u still feel like its not clear, u can post ur doubts here.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

I am getting the correct output without backtracking https://ide.codingblocks.com/s/288645

#9

@Vikaspal you have re-opened this doubt… What is the issue?

#10

@Ishitagambhir


this code is working without backtracking

#11

@Vikaspal what do you want me to do about it?

#12

@Ishitagambhir i video prateek bhaiya is using the backtracking to solve this problems.
if we do it will giving the duplicate permutations can u please checkout that…

#13

@Vikaspal yes by backtracking the permutations are not in sorted order, so to put them in sorted order and avoid repetition you can put all of the generated strings in a set and later print the set

#14

@Ishitagambhir nope i means, i the video using only recursion we are not able to generate all the permutation right?? some duplicate values is there like c permutation is missing here prateek bhaiya is using the char arr, but i not able to understand that how i am able to generate all possible permutation there without using the backtracking… ???

#15

@Ishitagambhir look at the code above

#16

@Vikaspal you are using a string, so there is no need to backtrack anyway. Sir was using an array which is passed by reference. But strings are passed as a copy so whatever changes you make in it will not be reflected in the previous parent function… i hope you are getting the point. If you pass the string by reference then you will also get the same wrong result as bhaiya got without backtracking.

#17

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.