This video demonstrates two things seldom seen in other explanations, and that makes this great! 1) The overlay of the translucent (low opacity) of the execution over the code, and 2) the inclusion of a detailed explanation of the execution. Well done; thank you!
You are correct bro there is mistake in video but its ok cause this teacher explain it in best way to help us understand this concept easily , thank you
1. This algorithm doesn't generate the permutations in sorted order, so I use a slightly different approach. 2. What is with all the negativity in the comments? I for one think you explain it very exhaustively. Thumbs up!
you can have explained recursion by showing the allocation and execution of stack for a single permutation or any reference video of stack allocation or execution.
Asking a sincere question, Please don't mind. While calculating Time complexity of the algorithm, it's coming out to be N * N! I am clear with N! For N (That's taking to print the string each time) I am having doubt. Generally printing of a string takes constant time. Please justify. Thank you in advance. You have done a great job.
+GeeksforGeeks I think the explanation is a little wrong. We are not backtracking from level 2 to level 1, as you mentioned at 2:18. You said we again "SWAP A and A" and come back to the original configuration, but backtracking is done while "SWAPPING B and B again" and " SWAPPING B and C again", after than no backtracking is done but "i" gets incremented and becomes 2 in For loop and A gets swapped with B which results in "BAC". Please check and explain me if i am understanding it wrongly. Thank you
+Ashish Kapil I see you're confusing the 'for-loop iteration where we move from left sub-tree of the root node to the middle sub-tree of the root node' with the 'backtracking step where we move from the level-1 of left sub-tree of the root node to the root node itself'. I hope this clears out your doubt, for a better understanding you might want to take a closer look at the dry run explained at 5:15.
Best explanation of this (permutation) and backtracking. I see now that backtracking is analogous to a depth-first traversal of a tree. I still don't quite understand Heap's permutation algorithm, which only has one swap instead of two, and that swap is slightly different depending on the even-odd parity of the string; I would appreciate if someone could respond with a sort of comparison of this with Heap's algorithm for permutations, which is very similar.
The way you've printed out Levels for each recursive call and dry run is very informative. Did you manually wrote this or used a piece of code to print out ? it would be very helpful in understanding recursion.
wow....i was searching for just this kind of stuff...thanks geeks for geeks...really quite a lucid explanation....actually none of the videos than i had gone through earlier this dry run and i was seeking for ythis only..really it was very useful
I wrote the code with and without the backtracking step. Both programs produce all combinations correctly. The order is different. The program without backtracking created a sorted output vs. the one with backtracking did not create sorted output.(note the last two elements - CBA vs CAB) So I am failing to see the importance of backtracking? Is this really required here? Code for reference (without backtrack) for(int i=posn;i
Could you please share the complete code? I ran the code without backtracking (code.geeksforgeeks.org/645xpY) and got the following output: ABC ACB CAB CBA ABC ACB
Here is the complete code (with backtrack) #include #include using namespace std; void permute(string input, int posn) { if(posn >= input.size()) { cout
public class Permutations extends Activity { String TAG = Permutations.class.getSimpleName(); char[] Res; int[] A; @Override protected void onCreate(@Nullable Bundle savedInstanceState) { super.onCreate(savedInstanceState); String input="ABC"; Res = new char[input.length()]; A = new int[input.length()]; perm("ABC".toCharArray(), 0); } void perm(char[] str, int k) { if (str.length == k) { Log.d(TAG, Arrays.toString(Res)); } else { for (int i = 0; i
When we call the permute function for the first time we pass two values: 0 and n-1. Inside the permute function, 0 is then assigned to L and n-1 is then assigned to R. L represents the starting index of the string to be permuted and R represents the ending index of the string to be permuted. First of all, inside permute, we check whether L==R to see if there's any thing left to permute. If L==R, we know that we have reached a Leaf Node of the Recursive Tree that was shown in the beginning. If L!=R, we know that we can there more than one characters to be permuted. So, we run a loop from L(eft) to R(ight) and at each step, we swap the element at position L with the element at the ith position.This modifies our string by the interchanging the positions of the character at Lth position and the character at ith position. However, in the first iteration of the loop, we notice that L=0 and i=0. So, the string has not yet been modified. But, we have come to one level below the root node of our Recursion tree. I request you to draw the recursion tree and see how the code takes you through the various nodes of the recursion tree. Feel free to ask more questions. :)
At level 1, how is it possible for the loop to run for i=0.We have given the initial value value of i=1. So the actual output should be OUTPUT BAC BCA CBA CAB
Do you want Palindrome substrings from a original Palindrome string or from a original non-palindrome string. If original string is palindrome each substring from i+k to length-k will be a palindrome where K varies from 1 to length/2.
That do work in java or python because every time a new space is created for the string in every recursion, but in C/C++ we are directly swapping those in the same address block of the memory which affects the order, so we need to swap it again to have the same order.
Thanks for your effort. Its fine. However, Mr tutorial maker, Your voice speed so robotically. You did not properly articulate the lecture. Otherwise everything is good.
The problem did not specify duplicated values or not. You can easily get rid of duplicated value by if(i>start&&arr[i]==arr[i-1])continue; after sorting original array
helo,how does your wriiten code work please explain #include using namespace std; void fun2(int n); int main() { int n=100; fun2(n); return 0; } void fun2(int n) { int LIMIT=1000; if (n LIMIT) return; cout
helo,how does your wriiten code work please explain #include using namespace std; void fun2(int n); int main() { int n=100; fun2(n); return 0; } void fun2(int n) { int LIMIT=1000; if (n LIMIT) return; cout
This is so robotic , there is no intuition , no insight , basically dry running !
Partially helpful !
i felt same.
This video demonstrates two things seldom seen in other explanations, and that makes this great! 1) The overlay of the translucent (low opacity) of the execution over the code, and 2) the inclusion of a detailed explanation of the execution. Well done; thank you!
vector result;
sort(S.begin(), S.end());
do
{
result.push_back(S);
} while (next_permutation(S.begin(), S.end()));
return result;
I think the i =2 case for Level 1 has a small mistake. Swapping A[0] and A[2] of ABC will give CBA. The video says CAB. Let me know if I am mistaken.
You are correct bro there is mistake in video but its ok cause this teacher explain it in best way to help us understand this concept easily , thank you
best ever explanation ever i watch for backtracking
1. This algorithm doesn't generate the permutations in sorted order, so I use a slightly different approach.
2. What is with all the negativity in the comments? I for one think you explain it very exhaustively. Thumbs up!
Very standard channel.. But don't know why very few subscribers.. people don't want to learn important difficult things.. want easy one..
you can have explained recursion by showing the allocation and execution of stack for a single permutation or any reference video of stack allocation or execution.
The audio is extremely bad. :(
Asking a sincere question, Please don't mind.
While calculating Time complexity of the algorithm, it's coming out to be N * N!
I am clear with N!
For N (That's taking to print the string each time) I am having doubt.
Generally printing of a string takes constant time.
Please justify.
Thank you in advance. You have done a great job.
it's not printing the string that is taking the time, it is the recursion which is going through the whole string, i.e N elements.
+GeeksforGeeks I think the explanation is a little wrong. We are not backtracking from level 2 to level 1, as you mentioned at 2:18.
You said we again "SWAP A and A" and come back to the original configuration, but backtracking is done while "SWAPPING B and B again" and " SWAPPING B and C again", after than no backtracking is done but "i" gets incremented and becomes 2 in For loop and A gets swapped with B which results in "BAC".
Please check and explain me if i am understanding it wrongly.
Thank you
+Ashish Kapil I see you're confusing the 'for-loop iteration where we move from left sub-tree of the root node to the middle sub-tree of the root node' with the 'backtracking step where we move from the level-1 of left sub-tree of the root node to the root node itself'. I hope this clears out your doubt, for a better understanding you might want to take a closer look at the dry run explained at 5:15.
Nicely explained..
please add interview question asked by the company during interview.
Thank you, Kaushal. We are working on adding videos on programming interview questions.
Very well explained sirji .... Thank you sir
I think there is a typo in the video :
For i = 2,
swap(A,C)
permute(CBA,1,2) // instead of permute(CAB,1,2)
swap(C,A)
+Pramod Srinivasan Thank you for pointing this out. You are right, it should be permute(CBA, 1, 2).
Ek dum Correct bro i was noticing ...when i was dry running code😎☺😊
can you please use a better mic from next time, audio volume is low and clarity is also not good.
Thank you for the feedback.
It is one of the very first videos we made, you will see that other videos on our channel have better audio quality. :)
Best Explanation ever, Thank you for shearing your knowledge with us...!
Best explanation of this (permutation) and backtracking. I see now that backtracking is analogous to a depth-first traversal of a tree.
I still don't quite understand Heap's permutation algorithm, which only has one swap instead of two, and that swap is slightly different depending on the even-odd parity of the string; I would appreciate if someone could respond with a sort of comparison of this with Heap's algorithm for permutations, which is very similar.
The way you've printed out Levels for each recursive call and dry run is very informative. Did you manually wrote this or used a piece of code to print out ? it would be very helpful in understanding recursion.
Thank you, Amox.
I wrote it down manually. But, I think using a piece of code to print the values of the variables at play is a fun thing to do.
wow....i was searching for just this kind of stuff...thanks geeks for geeks...really quite a lucid explanation....actually none of the videos than i had gone through earlier this dry run and i was seeking for ythis only..really it was very useful
its worst
why its n*n! ? if we are printing n times then it should be n + n! which eventually be n! only??
The very first loop is wrong, its supposed to be CBA not CAB, confused instead of explaining.
agreed
In level 1, and i=2, it should be CBA instead of CAB ( as per the tree in the beginning).
Let me know if my understanding is wrong.
u r right. even i noticed it. we moved back to original string and then came up for swaping.
well explained,thankyou so much
Best explanation on function call . thak you.
Excellent explaination sir
Thank you for the great explanation!
no its worst
Really like the solution and explanation. Thanks for this helpful video.
You're welcome, Heena.
if string contains same characters repeated, it would give extra cases. so use hash map
please see the subtitles around the 1:00 minute mark, it's strikingly wrong.
The captions or subtitles are generated by the RUclips algorithm so it's nobody's fault
It's also because of the perplexing accent of Indians!!
I wrote the code with and without the backtracking step. Both programs produce all combinations correctly. The order is different. The program without backtracking created a sorted output vs. the one with backtracking did not create sorted output.(note the last two elements - CBA vs CAB) So I am failing to see the importance of backtracking? Is this really required here?
Code for reference
(without backtrack)
for(int i=posn;i
Could you please share the complete code? I ran the code without backtracking (code.geeksforgeeks.org/645xpY) and got the following output:
ABC
ACB
CAB
CBA
ABC
ACB
Here is the complete code (with backtrack)
#include
#include
using namespace std;
void permute(string input, int posn)
{
if(posn >= input.size())
{
cout
It depends on whether you're creating a new string in your swap method or not. If you work on the same character array, you have to backtrack.
please continue uploading videos. This was very nice..
+Jitendra Baug Thank you!
We are working on adding more videos. Stay tuned.
background noise is so annoying,but thanks for making the video it helped me alot
Regarding time complexity.I had a doubt , How can printing the string became O(N).it should be O(1).Please clarify!
great, next time do it with sound
Good explanation sir
very nice videos can you upload solutions of programming questions asked in amazon,google etc?
Thank you, Vidhit. We are working on adding videos for programming interview questions.
Please remove the background noise , It's too Anoying ! anyways good job .
how to eliminate duplicate combinations?
use set
public class Permutations extends Activity {
String TAG = Permutations.class.getSimpleName();
char[] Res;
int[] A;
@Override
protected void onCreate(@Nullable Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
String input="ABC";
Res = new char[input.length()];
A = new int[input.length()];
perm("ABC".toCharArray(), 0);
}
void perm(char[] str, int k) {
if (str.length == k) {
Log.d(TAG, Arrays.toString(Res));
} else {
for (int i = 0; i
sir can you tell me which type of program i have to prepare for MAQ Software test,,,your all videos are help me???
To much noise
i cant understand that recursive part (permute)..cud u plz explain me sir,,i dunno how the value of l retains at 0 itself...need answers plz
When we call the permute function for the first time we pass two values: 0 and n-1. Inside the permute function, 0 is then assigned to L and n-1 is then assigned to R. L represents the starting index of the string to be permuted and R represents the ending index of the string to be permuted.
First of all, inside permute, we check whether L==R to see if there's any thing left to permute. If L==R, we know that we have reached a Leaf Node of the Recursive Tree that was shown in the beginning. If L!=R, we know that we can there more than one characters to be permuted. So, we run a loop from L(eft) to R(ight) and at each step, we swap the element at position L with the element at the ith position.This modifies our string by the interchanging the positions of the character at Lth position and the character at ith position.
However, in the first iteration of the loop, we notice that L=0 and i=0. So, the string has not yet been modified. But, we have come to one level below the root node of our Recursion tree. I request you to draw the recursion tree and see how the code takes you through the various nodes of the recursion tree.
Feel free to ask more questions. :)
Audio quality worst.. I didn't expect this from g2g.... Come on guys u ppl worth a lot.. Don't let these small things to spoil ur work....
Thank you for your feedback, Kiruba.
For those of you complaining about the video - here is an alternative: ruclips.net/video/78t_yHuGg-0/видео.html
plz do make practical approach clear.it's confusing..
Will it provide correct results in case of characters repetition in given string?
+Sheetal No it won't , answers will be in repitition
I think the second ` str = Swap(str, l, i);` is not requied...
At level 1, how is it possible for the loop to run for i=0.We have given the initial value value of i=1. So the actual output should be
OUTPUT
BAC
BCA
CBA
CAB
I see you're confusing i=l (L in small alphabets) with i=1 due to the font used in the code.
The loop is running from i=l (signifying left) to i
Thanks
You're welcome, Harshit!
Can you please use a better mic and can speak clearly then it will help us a lot .TIA
why we have swap for backtracking. Can you plz check without this swap. I think it'll work without this second swap also.
Awesome.....keep up the gud work guys..
Thank you, Madhuri!
very helpful...
Thank you!
i want to store the value of permutation then print it
can you bit slow so that we can understand it better.
Could we do it using bfs or dfs
have you done this in java?
recursive calls to permute function again and again is very confusing. try to explain step by step
i think the solution is wrong. Think if there are any repetition.
If i give input : AAB
Output Should be: AAB ABA BAA
BUT Your output: AAB ABA AAB ABA BAA BAA
and it should be like that. Cuz the order is important. which means with a 3 letter's word, there should be 6 permutations
Well done sir
how can we find all possible palindromic partitions of given string?
nitin
n i t i n
n iti n
nitin?
Following resource might help you: www.geeksforgeeks.org/given-a-string-print-all-possible-palindromic-partition/
Do you want Palindrome substrings from a original Palindrome string or from a original non-palindrome string.
If original string is palindrome each substring from i+k to length-k will be a palindrome where K varies from 1 to length/2.
can someone please tell me the use of the second swap line, as I'm getting the same output without adding 2nd swap too
That do work in java or python because every time a new space is created for the string in every recursion, but in C/C++ we are directly swapping those in the same address block of the memory which affects the order, so we need to swap it again to have the same order.
could have used a different font... cant differentiate 1 and L .....
Sir is this series enough for India Computing Olympiad?
Thanks for your effort. Its fine. However, Mr tutorial maker, Your voice speed so robotically. You did not properly articulate the lecture. Otherwise everything is good.
Can we do this without function
Please remove the background noise , It's too Anoying ! anywise good job .
great work
Thanks, Yuvraj! :)
very nice thank u so much
Thanks for the video :)
But most importantly it won't work for repeated characters....its simply showing values for n! times
The problem did not specify duplicated values or not. You can easily get rid of duplicated value by if(i>start&&arr[i]==arr[i-1])continue; after sorting original array
helo,how does your wriiten code work please explain
#include
using namespace std;
void fun2(int n);
int main()
{
int n=100;
fun2(n);
return 0;
}
void fun2(int n)
{
int LIMIT=1000;
if (n LIMIT)
return;
cout
is there any better approach to solve this question...
Yes, you can use prefix-remaining approach:
github.com/yask123/interview_prep_python/blob/master/permutate.py
best video explain this!
thanks
You're welcome! :)
Thanks you. But the MIC!
That's a really poor explanation....but thumbs up for the code snip
speed 0.75
If you can not explain then don't try to do so
I think this tutorial is not so good, try for individual string.
this person is simply running . very poor explanation
为什么这种视频全是印度口音
因为贡献者是印度人:)
deii oru mayirum puriyala da thelivaa sollu da
her i = 0
it seems that you are in hurry to make this video. dislike for your explaination!!!!!!!
worst xplanation
helo,how does your wriiten code work please explain
#include
using namespace std;
void fun2(int n);
int main()
{
int n=100;
fun2(n);
return 0;
}
void fun2(int n)
{
int LIMIT=1000;
if (n LIMIT)
return;
cout