String Permutation Algorithm
HTML-код
- Опубликовано: 30 сен 2024
- / tusharroy25
github.com/mis...
github.com/mis...
github.com/mis...
www.educative....
Write a code to generate all permutations of given string in lexicographically sorted order with repetition of characters in the string.
came looking for guitar techniques (finger permutations)
stayed for the computational algorithms
Unbelievable....Awsome
lol.
Hahaha
😂😂
lol
ghood man ghood, you are rheally an amazing theacher, hats off to you thushar...
Amazing work, thanks for all the effort you've put into making this video!
Awesome Video Tushar :) Excellent explanation of code . Now my concept is clear .
Very good explainations! Thank you very much for taking the time to make this videos! *thumbsup*
How do you make the GUI in which you were explaining the working of the code? Its a really cool way of explaining things :)
I got lost 4:51, wait, can someone explain me why not start at third depth ..? please...
YOur Videos are awesome
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.
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 feel happy every time there is something I don't understand and there is a video by you explaining it. :)
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
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.
Your effort is highly appreciable :)
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 :)
For anyone interested in a JavaScript implementation: gist.github.com/sghiassy/669cae13af2632a3ee16b0c633982343
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!!!
thanks bro, usually I set 1.25 speed for youtube videos, but for you, I have to set 0.75. lol.
Definitely appreciate the effort this guy has put in. I havent seen anyone teaching with so much patience.
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.
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.
this is an awesome explanation hat off Tushar
Hi, Thanks for the explanation. I have a doubt too, I was trying it for input AABC, but according the coding logic given, result arrays is of size 3 and prints the combination in 3 letters combination, but isn't the output supposed to be 4 letters combinations?
What is the goddamn time complexity my man?
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.
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!
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.
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!
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.
Excellent explanation .. Thanks for putting so much effort to explain :)
HI Tushar, its very helpful but can u please write the code in c++
Made a detailed video explaining a general method to solve backtracking problems that would be helpful to watch after this here ruclips.net/video/fahWlqwOvHo/видео.html
One more soultion:
import java.util.*;
class PermutationDupPrintWithoutDup{
public static void main(String[] args){
String s="AABC";
HashMap hm=new HashMap();
for(int i=0;i0){
hm.put(c,count-1);
PrintPerm(hm,prefix+c,remaining-1);
hm.put(c,count);
}
}
}
}
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");
}
Try with this solution
public class Permutaion {
public static void main(String[] args) {
permutate("AABC".toCharArray(),0,3);
}
public static void permutate(char c[],int l,int r){
if(l==r){
System.out.println(c); }
else{
for(int i=l;i
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.
0:33 What formula is this? If we have AABC, we will have 4!/2! permutations, or 12 permutations. It makes sense, bc if we had 4 unique letters, we would have 4! permutations, but since we have 2 A's, we divide by 2. But what is the formula?
what I am not convinced about is why should we manually increment the count[i] at the end of the recursion? Won't the previous recursion state of this count will be persisted just like result[] ? Why should we manually decrement 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.
Great video..but there's a mistake in code.. you need to make two recursive calls in permuteUtil otherwise your code would print only one combination i.e. aabc
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
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);
}
My first comment on youtube! This is a great effort and a very helpful one indeed! Thank you!
Can anyone explain how the run time is O(n!) not by knowing the problem statement but just by looking at the code.
But the time complexity is O(alphabet size ^ string length) since for each index we need to go through whole alphabet?
You are amazing.. Thank you for 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. :)
i have been struggling to understand this,i can't tell u how glad I am to u I found this video.
for code in c++:
refer : ideone.com/5apaZ6
problem link: leetcode.com/problems/permutations-ii/#/description
can anyone give me code substitute for this program in c???? plllssss!
My implementation in python: github.com/andresesfm/coding_challenges/blob/master/Tushar/test_string_permutations.py
Dude, this video helps hell out of me, thanks!
Leetcode Solution using this method in C++:
pastebin.com/FM1Q2WKU
Phenomenal example here especially covering duplicates. Very helpful Tushar.
use of count[i]++ in your code??
sir ur pronunciation is good but now a days u r faking it a lot. its naturally good u need not do that
Thanks for the video.it's very helpful
Thanks a lot. Amazing clarity in explanation :)
How do we calculate the time complexity of this solution?
//C++ IMPLEMENTATION of the above concept
#include
using namespace std;
string str="abcde";
string out=str;
void permute(int arr[],int l,int n,int x)
{ x++;
if(l==n)
{ cout
wAh
thank you so much to doing such type of videos really great work..thanks..thanks..thanks.!
Best teacher :)
he is god sent!
This look really messy... thank you though!
skip to 17:56 if you wanna skip whole permutations
Is this algorithm based on DFS? Characters are kind of marked as seen when their counts are at 0 and skipped. The result of a processed node is then pushed onto the recursion stack. I guess in this case though the count is reset to continue permuting. So maybe this Backtracking? Idk I'm new to these exhaustive algos.
JavaScript Implementation
function normalizeString(str) {
let map = new Map();
for (let char of str) {
if (!map.has(char)) {
map.set(char, 1);
} else {
map.set(char, map.get(char) + 1);
}
}
let newStr = [...map.keys()].join("");
return [newStr, map];
}
function permutations(str) {
if (!str.length) {
return null;
}
// remove dups and creaste count arr;
let [newStr, countMap] = normalizeString(str);
const results = [];
const result = [];
function backtrack(s, level) {
for (let i = 0; i < s.length; i++) {
let char = s.charAt(i);
if (countMap.get(char) > 0) {
countMap.set(char, countMap.get(char) - 1);
result[level] = char;
backtrack(s, level + 1);
countMap.set(char, countMap.get(char) + 1);
result[level] = null;
}
}
// it will be called when for loop is finished that means all is 0
if (level === str.length) {
results.push([...result]);
}
}
backtrack(newStr, 0);
return results;
}
console.log(permutations("aabc"));
Thanks for the video , nice explain.
But I have a question on the code, should the 'result' pop back character after the recursive ?
I used javascript to implement, if not pop back , the result is wrong. So I add 'result.pop()' after "count[i]++", then the result is right.
where can i find the c++ code for this problem
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
Clear presentation, thank you!
Brother i tell one programe please solve it to help me bro that programe is input =5,and string input is =5 output is aabbc, abbbc, aaabc, abbbc etc i dont know this programe pls help me bro
Hello Tushar
Thanks for all your great informative videos.
Could you please share me the application name you used for coding in this video.
This will really help me to teach my students.
Vishal
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.
thiis man can be a good student not good teacher
Shouldn't the last items in your result reset when you backtrack? Previous iteration uses a local variable that doesn't of what's on index 3 for example.
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.
I know you wouldn't read this comment , but still another great vid. Thanks Man!
can you do the additive sequence problem? search for leetcode additive number string to see the problem link on google
I am still not sure why the runtime would be big O of n factorial, can anyone explain please? thank you
shouldn't the time complexity be O(m*n!), where m represents the length of the string without duplicates?
You could use Syster.out.println(Arrays.toString(result));
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
thanks sir. your videos are very insightful and explain every aspect of the problem statement
Finally understood how to go about a backtracking tree. Very helpful thank you!
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
If ,we are asked to print Permutation taking r at a time, then can we change the printing condition form (level ==result.length) to (level==r) ??.
please explain, when level=result.length, where exactly the Control RETURNS to?
not able to understand the return call here.
to the upper level of recursion tree. each time recursion is called u go a level deeper into the tree. so when u return to go a level higher .....
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.
Guy ... Your effort is highly apreciated
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
great explanation tushar _/\_
Hi Tushar, I believe, this is not an efficient solution in terms of running time. Any thoughts?
First of all, thanks for your reply.. :)
I am new to DSA so please correct me if my understanding is wrong. I tried running the program for the following input and it takes noticeable time to complete execution.
252, 632, 262, 707, 506, 701, 475, 410, 696, 631, 903, 516, 149, 344, 101, 42, 891, 991, 555, 652
I believe that running time is O(n!) and with this understanding I was wondering that if there is a better solution.
well explained and well-illustrated. Though the theory part at 2:00 was a bit hard to digest.
what is the prerequisite algorithm should be learnt before doing this problem
can any one tell me plz
Awesome!
I have a question in the python code. How can I store these values in a variable?
Whichever way I try to append the result to a list, it always ends up appending only the last term, not all of them.
Where do you get all your algorithms? Do you use a text book or any other source?
Nice Video Tushar. You videos always increase the level of my understanding. Thanks :)
Anyone know what the algorithm is actually called?
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.
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;