A lot of online lectures of great universities expect us to be smart, so they don't go into the problems as detailed. But yes, many of us are that stupid and videos like this are exactly what we need. Really helps me visualize and understand recursion better. Thanks!
Nobody is smart in every way, there's bound to be lots of people who can benefit and make use of the knowledge that would find some of the more abstruse or obscure presentations useless to them. This is a great video.
I've watched many algorithm tutorial videos and this is one of the best. Really appreciate how thorough and detailed it on top of presenting it in an organized manner.
Too complicated. This is much simpler! // Found at a UFO crash site. // All permutations of 5 items generated. #include #define N 5 int main(void) { int X[N], Y[N]; for (int n = 0; n < N; n++) X[n] = Y[n] = n; Show: for (int n = 0; n < N; n++) printf(" %d", X[n]); putchar(' '); for (int n = 0; n < N; n++) { int Xn = X[n]; X[n] = X[Y[n]], X[Y[n]] = Xn; if (--Y[n] >= 0) { int Xn = X[n]; X[n] = X[Y[n]], X[Y[n]] = Xn; goto Show; } Y[n] = n; } return 0; } (The aliens cited are over here: ruclips.net/video/9dTDhCKBA_c/видео.html )
@@RockBrentwood That's basically the same concept except using nested for-loop instead of recursion. Also the variable names are so obscure, it's more difficult to read than Tushar's code at the end of the video.
I am searching a good algorithm for permutation from last 2 years but I found noting good. But at last I find a good way from here. Your lectures are awesome.
The algorithm is: Remove the first letter Find all the permutations of the remaining letters (recursive step) Reinsert the letter that was removed in every possible location
Nice explanation, Incase if any one missed the following point Sorting of the given input string is done through Treemap. permuteUtil function prints distinct permutations of a string lexicographically only when the input string is sorted.
thank you! earlier i was reading this code in quora and i could not understand what the author was doing .. but now through your visuals i understood it better and completely. Thanks again;
Thanks! I went looking for a tutorial on this algorithm thinking I'd have to watch it several time to get it but really understood it in the first 10 minutes. Great video!
Simply amazing videos. I tried to get the feel of recursion for ages, and finally your video did it. Really love the format of your videos and your step-by-step approach of explanation is really what makes learning fun. I have tried other channels like saurabhschool etc, but your explanation suits me more. One minor suggestions though: if after each video you can leave us with practice problems of similar kind. For example, now I've understood this problem and can code it easily. But it will really make my understanding even better if I can apply this knowledge to 2-3 different problems (which uses the same logic). So few practice problems of similar kinds would help.
Great video - thank you! As you expand the permutation graph, I'd suggest you add some sort of 'divider' (removal tape?) to provide an indicator of level. great content!
Hello, The only missing thing I guess is you do not clear the last value in "result" array when backtrack happens. Using stack seems more appropriate I guess. Thanks for the share. You did very good job!!!
Easy summary: 1) when going into recursion, find leftmost non zero count. 2) when coming out of recursive call, first move pointer 1 step ahead and then find first non zero count. :)
According to his algorithm its more like O(k^2 * k!). There are k*k! function calls, but each function loops through k times to see what values have been used before.
In this case, The counts determine the how many times we can use the character there by eliminating the dups in the output. the character counts along with stack level which controls the result table will decide the permutation. The first for loop will ensure the order of the output. Just sharing my understanding
This is a very intuitive and understandable algorithm. However, it is not optimal for space complexity due to the extra count[] array to store which chars are used or not. There are more space efficient algorithms for permutation.
thanks for the awesome explanation. a suggestion in program: we can reduce num of lines in Hash map compute to: for (int k =0; k < input.length; k++) { countMap.put(input[k], occurence.getOrDefault(input[k], 0) + 1); }
Tushar, can you please make these days a video about P, NP, NP complete and NP hard algorithms? From you i can understand them much better than even my university professors. Thank you!
This is exactly how this should be explained. Although it could have helped if you explain what happens if we dont use a count for the repeated elements. In the case we don't , the permutations are repeated.
Bhai tu hai kaun, Kaha sey aaya hai, , what an awesome stuff to start the permutaion and combination of strings.bro u killed it....cant find any better explanation than yours to simple looking complex implementation of this problem.. cheers to u yarr
Great video as usual! Could you make time to create video about big numbers (adding, subtracting, multiplication and division)? It would help a lot of guys using c++
I really appreciate your effort. Thank you for sharing knowledge. It's the best thing in the world. It would be great if you can share your view about some standard design pattern problem (How one should approach to solve the problem.) For Example, Pub-sub design pattern with concurrency which should be easy to scale for million of topic, messages, subscribers.
Hi Tusar Sir, You made DS topics so simple with your explanation. I want to ask you the complexity of this algorithm. and May you please create some video on complexity. Thank You.
Hey Tushar, nice video as always! But for next one could you do about Big Integer problems. I really like to know your tips for this kind of problem when using C++.
it's a class in java to store the big numbers which are not fitting in memory ,I don't know much about it because they don't need it in IOI but it's neseccary for ACM (sorry for my bad english)
Soooo...Cantors diagonal argument that proports to prove that there are many infinities relies on just such a list. The problem is that for Cantor to be right the list of permutations MUST be square. That is to say each row must have the same number of entries as each column in order to, diagonally, cover every possible permutation in the list. But as we can see, any such list of permutations on a set (row) will grow by the factorial downwards as it iterates to the right by the addition of each singular element bitwise. This process can never produce a square matrix. Diagonalization never 'works' (produces a new or unique combination of set elements) in the finite world. And to produce aleph null in the first place we must turn to Zermelo where we are guaranteed a very basic, naive and the most axiomatic notion of infinity arrived at by process of....wait for it...iteration. Cantors diagonal argument is a wonderful bit of sophistry certainly. But it is not based on any real or even theoretically possibly constructable list. An infinite world of infinities is a semantic mobius strip.
Hi verygod , but @21.35 needed to explain about backtracking , how permute(0,1,1) count[i--] -->permute(0,0,0) prints -->permute(0,0,1)(i who does count[i++] to be back in state , this one is missing in explanation of code.
Hi Tushar, Your technique and explanation is very good and thoughtful. I just have one concern here that the explanation and the code part does not go hand in hand. In explanation you said the algo does not give duplicates but in the code you said it will give duplicates. Can you please provide the code as per the explanation. Thanks
According to his algorithm its more like O(k^2 * k!). There are k*k! function calls, but each function loops through k times to see what values have been used before.
Hi Tushar, many thanks for your efforts. Would this be the same approach for integer arrays ? Could you do a video that considers integer array permutations ? Thanks.
Hi Modifications needs to be done . Your code cannot handle duplicates if any in array it gives arrayoutofbound exception ... Solution to it is While defining length of count[] and str[] it should be char str[] = new char[str.length]; int count[]= new int[str.length]; and not char str[] = new char[countmap.size()]; and to print all the permutations in lexicographical order PASS the SORTED STRING
came looking for guitar techniques (finger permutations)
stayed for the computational algorithms
Unbelievable....Awsome
lol.
Hahaha
😂😂
lol
A lot of online lectures of great universities expect us to be smart, so they don't go into the problems as detailed. But yes, many of us are that stupid and videos like this are exactly what we need. Really helps me visualize and understand recursion better. Thanks!
Nobody is smart in every way, there's bound to be lots of people who can benefit and make use of the knowledge that would find some of the more abstruse or obscure presentations useless to them. This is a great video.
No they simply don't have the time and so they expect you to do your own research. Although I do think they should provide a reference.
i have been struggling to understand this,i can't tell u how glad I am to u I found this video.
I feel happy every time there is something I don't understand and there is a video by you explaining it. :)
I've watched many algorithm tutorial videos and this is one of the best. Really appreciate how thorough and detailed it on top of presenting it in an organized manner.
Definitely appreciate the effort this guy has put in. I havent seen anyone teaching with so much patience.
Cool. This tutorial made me understand backtracking like charm. Hats off tushar.Keep doing the good job
Too complicated. This is much simpler!
// Found at a UFO crash site.
// All permutations of 5 items generated.
#include
#define N 5
int main(void) {
int X[N], Y[N];
for (int n = 0; n < N; n++) X[n] = Y[n] = n;
Show:
for (int n = 0; n < N; n++) printf(" %d", X[n]); putchar('
');
for (int n = 0; n < N; n++) {
int Xn = X[n]; X[n] = X[Y[n]], X[Y[n]] = Xn;
if (--Y[n] >= 0) {
int Xn = X[n]; X[n] = X[Y[n]], X[Y[n]] = Xn; goto Show;
}
Y[n] = n;
}
return 0;
}
(The aliens cited are over here: ruclips.net/video/9dTDhCKBA_c/видео.html )
@@RockBrentwood That's basically the same concept except using nested for-loop instead of recursion. Also the variable names are so obscure, it's more difficult to read than Tushar's code at the end of the video.
Finally understood how to go about a backtracking tree. Very helpful thank you!
I am searching a good algorithm for permutation from last 2 years but I found noting good. But at last I find a good way from here. Your lectures are awesome.
ghood man ghood, you are rheally an amazing theacher, hats off to you thushar...
Phenomenal example here especially covering duplicates. Very helpful Tushar.
The algorithm is:
Remove the first letter
Find all the permutations of the remaining letters (recursive step)
Reinsert the letter that was removed in every possible location
how you would first permutation of rest letters
I have seen your other videos and I've learnt from them a lot, but, this is by far the best one! Thanks so much, Tushar.
He will not go trough all permutations, no way .... Wait...he is 😀
:) :) LOL!!!
Actually I think it is important for us since it helps us understand recursion much more clearly.
Your efforts are highly appreciable sir
This was the best explanation I could find on RUclips. Thanks Tushar !
look for the Stanford video on backtracking.. thats good too
My first comment on youtube! This is a great effort and a very helpful one indeed! Thank you!
Thanks Tushar, this really helped me to understand completely which I didn't understand from anywhere
Nice explanation,
Incase if any one missed the following point
Sorting of the given input string is done through Treemap. permuteUtil function prints distinct permutations of a string lexicographically only when the input string is sorted.
this is an awesome explanation hat off Tushar
thank you! earlier i was reading this code in quora and i could not understand what the author was doing .. but now through your visuals i understood it better and completely. Thanks again;
Guy ... Your effort is highly apreciated
Thanks! I went looking for a tutorial on this algorithm thinking I'd have to watch it several time to get it but really understood it in the first 10 minutes. Great video!
Your effort is highly appreciable :)
Simply amazing videos. I tried to get the feel of recursion for ages, and finally your video did it.
Really love the format of your videos and your step-by-step approach of explanation is really what makes learning fun.
I have tried other channels like saurabhschool etc, but your explanation suits me more.
One minor suggestions though: if after each video you can leave us with practice problems of similar kind.
For example, now I've understood this problem and can code it easily. But it will really make my understanding even better if I can apply this knowledge to 2-3 different problems (which uses the same logic). So few practice problems of similar kinds would help.
Great video - thank you!
As you expand the permutation graph, I'd suggest you add some sort of 'divider' (removal tape?) to provide an indicator of level.
great content!
Hello,
The only missing thing I guess is you do not clear the last value in "result" array when backtrack happens. Using stack seems more appropriate I guess.
Thanks for the share. You did very good job!!!
Awesome Video Tushar :) Excellent explanation of code . Now my concept is clear .
Best algorithms channel by individual contributor!
Excellent explanation .. Thanks for putting so much effort to explain :)
Structured, simple and thorough...... Great job!
Nice Video Tushar. You videos always increase the level of my understanding. Thanks :)
brilliant. Its quite difficult/tedious to visualize recursion. This video helps a lot! Thanks
Amazing work, thanks for all the effort you've put into making this video!
Easy summary:
1) when going into recursion, find leftmost non zero count.
2) when coming out of recursive call, first move pointer 1 step ahead and then find first non zero count. :)
According to his algorithm its more like O(k^2 * k!). There are k*k! function calls, but each function loops through k times to see what values have been used before.
Thank you so much Tushar! Finally I understand how it works.
Great Job!! He frickin backtracked all the permutations manually.
thanks sir. your videos are very insightful and explain every aspect of the problem statement
I cant't thank you enough for the awesome videos that you make !!
In this case, The counts determine the how many times we can use the character there by eliminating the dups in the output.
the character counts along with stack level which controls the result table will decide the permutation. The first for loop will ensure the order of the output. Just sharing my understanding
This is a very intuitive and understandable algorithm. However, it is not optimal for space complexity due to the extra count[] array to store which chars are used or not. There are more space efficient algorithms for permutation.
Thanks a lot. Amazing clarity in explanation :)
thanks for the awesome explanation. a suggestion in program:
we can reduce num of lines in Hash map compute to:
for (int k =0; k < input.length; k++) {
countMap.put(input[k], occurence.getOrDefault(input[k], 0) + 1);
}
the very easiest way you have explained this solution. Thanks
Tushar, can you please make these days a video about P, NP, NP complete and NP hard algorithms? From you i can understand them much better than even my university professors. Thank you!
This is exactly how this should be explained.
Although it could have helped if you explain what happens if we dont use a count for the repeated elements.
In the case we don't , the permutations are repeated.
Clear presentation, thank you!
Dude, this video helps hell out of me, thanks!
Tushar it's simply awesome... i like your explanation.....
Nice algorithm. Good work. It helped me for my interview!
Best explanation on this topic ever!!
Great video! Your explanation is so clear! Thank you!
wonderfully elegant solution
The best solution that you can find in Internet.
Bhai tu hai kaun, Kaha sey aaya hai, , what an awesome stuff to start the permutaion and combination of strings.bro u killed it....cant find any better explanation than yours to simple looking complex implementation of this problem.. cheers to u yarr
Keep doing. You are the best teacher
Very good explainations! Thank you very much for taking the time to make this videos! *thumbsup*
Thank you Tushar! Please upload more great videos!
great lecture makes recursion so much simpler. Love it thanks for this :)
Great video as usual!
Could you make time to create video about big numbers (adding, subtracting, multiplication and division)?
It would help a lot of guys using c++
+Tushar Roy Yes, for example to be able to solve SPOJ problem JULKA
I suggest just use Java for big numbers, it's very simple.
I agree, but I wanted to see the algorithm in action.
Division gives me headache :)
Great explanation!! Best
I really appreciate your effort. Thank you for sharing knowledge. It's the best thing in the world. It would be great if you can share your view about some standard design pattern problem (How one should approach to solve the problem.) For Example, Pub-sub design pattern with concurrency which should be easy to scale for million of topic, messages, subscribers.
You are a legend, thanks for making these.
Thanks for the video.it's very helpful
Brilliant explaination. Keep up the good work.
awesome Tushar .. awesome .. really appreciate your efforts (Y)
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
public static void main(String args[]) {
permutation("AABC");
}
You are amazing.. Thank you for this video !!!!
Great Work!!! I really like your videos. Thanks Man.
Awesome stuff! This really helped my understanding!
Very good explanation.. Thanks..
your work is really good. Thank you and keep going
thanks bro, usually I set 1.25 speed for youtube videos, but for you, I have to set 0.75. lol.
Hi Tusar Sir, You made DS topics so simple with your explanation. I want to ask you the complexity of this algorithm.
and May you please create some video on complexity.
Thank You.
thank you so much to doing such type of videos really great work..thanks..thanks..thanks.!
Hey Tushar, nice video as always! But for next one could you do about Big Integer problems. I really like to know your tips for this kind of problem when using C++.
it's a class in java to store the big numbers which are not fitting in memory ,I don't know much about it because they don't need it in IOI but it's neseccary for ACM (sorry for my bad english)
numbers of size greater than 64 bit, in C++ there is no datatype to store and perform operation on it ?
Soooo...Cantors diagonal argument that proports to prove that there are many infinities relies on just such a list. The problem is that for Cantor to be right the list of permutations MUST be square. That is to say each row must have the same number of entries as each column in order to, diagonally, cover every possible permutation in the list. But as we can see, any such list of permutations on a set (row) will grow by the factorial downwards as it iterates to the right by the addition of each singular element bitwise. This process can never produce a square matrix. Diagonalization never 'works' (produces a new or unique combination of set elements) in the finite world. And to produce aleph null in the first place we must turn to Zermelo where we are guaranteed a very basic, naive and the most axiomatic notion of infinity arrived at by process of....wait for it...iteration. Cantors diagonal argument is a wonderful bit of sophistry certainly. But it is not based on any real or even theoretically possibly constructable list. An infinite world of infinities is a semantic mobius strip.
Awesome explanation !!
Many Thanks Tushar.............. Keep up the good work.....best videos :)
Very well explained. Thank you.
Between here is the link to handle duplicates using different logic : gist.github.com/MBJAVA/87d1ae03a9e0865589473c0aad56d255
Hi verygod , but @21.35 needed to explain about backtracking , how permute(0,1,1) count[i--] -->permute(0,0,0) prints -->permute(0,0,1)(i who does count[i++] to be back in state , this one is missing in explanation of code.
he is god sent!
great explanation tushar _/\_
Really helpful explain, thank you for the tutorial
Hi Tushar,
Your technique and explanation is very good and thoughtful.
I just have one concern here that the explanation and the code part does not go hand in hand. In explanation you said the algo does not give duplicates but in the code you said it will give duplicates. Can you please provide the code as per the explanation.
Thanks
Runtime complexity will actually be O(K * k!), where K = # unique elements in a string
According to his algorithm its more like O(k^2 * k!). There are k*k! function calls, but each function loops through k times to see what values have been used before.
Great video Sir. You earned an subscriber. :)
Appreciate your effort!
thanks a lot ,
that's really helpful to get a understand the concept,
+Tushar Thanks you so much. waiting for more design related videos..
Hi Tushar, many thanks for your efforts. Would this be the same approach for integer arrays ? Could you do a video that considers integer array permutations ? Thanks.
Indian teachers always there to save a day...
I know you wouldn't read this comment , but still another great vid. Thanks Man!
well explained and well-illustrated. Though the theory part at 2:00 was a bit hard to digest.
great explanation. Thanks!
hatsoff to your hard work sir
such a good explanation!!
Hi Modifications needs to be done . Your code cannot handle duplicates if any in array it gives arrayoutofbound exception ... Solution to it is While defining length of count[] and str[] it should be
char str[] = new char[str.length];
int count[]= new int[str.length];
and not char str[] = new char[countmap.size()];
and to print all the permutations in lexicographical order PASS the SORTED STRING
This is great. Thank you.