I have two questions -
1.) When we use string instead of char array why dont we need to use backtracking?
2.) I am not able to understand that when we give ‘abc’ as input in the above code then cab is printed before cba which is not the case in when we take char array rather than string as shown in the video. Even when i dry run the above code with abc as input i infer that cba should come before cab but it is not the case. Why is this so?
as in case of using a char array u will be backtracking else the same problem of repeating combination is seen
using namespace std;
void permute(char a[], int l, int r)
{
if (l == r)
cout<<a<<endl;
else
{
for (int i = l; i <= r; i++)
{
swap(a[l], a[i]);
permute(a, l+1, r);
swap(a[l], a[i]);
}
}
}
int main()
{
char str[100];
cin >> str;
int n= 0;
for(int i = 0 ; str[i] != '\0'; i++)
n++;
permute(str, 0, n-1);
return 0;
}
we see that cab comes before cba
and even lexographically cab comes before cba
I understood why we need backtracking when we use char array but I have asked why we don’t need backtracking when we use string instead of char array
Also in the dry run (the picture which you have attached) we can see that cba comes before cab so why is cab printed before cba when we use string data type rather than char array. (What I am trying to ask is that when we use char array as the data type cba is printed before cab but when we use string data type cab is printed before cba, why is this so? isn’t the dry run for both the data types same, so why are we getting different outputs.
we need backtracking in both the cases, u can see i have attached code for char array and u have written for stirng both need backtracking
bro u are writing a different version of the code when u get cab before cba
for (int i = l; i <= r; i++)
{
// Swapping done
swap(a[l], a[i]);
// Recursion called
permute(a, l+1, r);
//backtrack
swap(a[l], a[i]);
}
if u use this for both char array and string u get cba before cab
i hope this is clear now i hope so.
I haven’t used backtracking for string data type still it is printing all possible permutations.
All I am trying to ask is that if we remove the backtracking swap then some permutations should repeat as shown in the video (in the video char array is used) , but it prints all possible permutations without repeating even when we not use backtracking case (when we use string data type)
I hope I am able to explain my doubt…
The full explanation is in the ide below
I get it that cba comes before cab in both cases,
I guess I haven’t explained my question properly,
it is explained in the IDE below
listen to bhaiya at 10:40 time
char array is passed as reference while in ur code string is passed by value hence u dont require backtracking to produce all combination
thanks I got this, but if possible can you explain a dry run for this program
I just want to know how this program is working as in that when i dry run this for input abc on paper I am getting a diff output than what the actual output is, so it would be really helpful if you could dry run this for abc as inout and explain the reason it is giving the output that it is giving.
@Ak07
mera bhi cba pehle araha h
probably we are going wrong some where,
one thing i suggest u dont go soo deep in 1 question that u spend 24 hr on it
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.
