heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
// I just saw the recursive tree and implemented it in my way : const result = []; function permutation(arr, ans = [], level = 0) { if (ans.length === arr.length) { result.push([...ans]); return; } const ele = arr[level]; // element to be placed according to the current level for (let i = 0; i < ans.length; i++) { ans.splice(i, 0, ele); permutation(arr, ans, level + 1) ans.splice(i, 1); } ans.push(ele); permutation(arr, ans, level + 1); } permutation([1, 2, 3]); console.log(result)
When doing the big O for space, I see you take into account the slice that's on line 5, what about the slices on within the forEach on line 13? do we not take those into account when calculating space?
YOU WERE THE ONE THAT MADE ME understand perm/comb and dp :) I know you did a lot and I just gave you likes and sub BUT I still want to suggest you to do : Backtracking :) thanks
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
create a Memo variable, coderbyte have a excelent explanation too about this implementation in their Dynamic Programming course video th-cam.com/video/oBt53YbR9Kk/w-d-xo.html
@@borisbarzotto5785 heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
Isn't space complexity is also O(n!)? We kind of accumulating all possible permutations (all n! of them). It even might be O(n*n!) since we doing it for each recursive function call
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
For those who use Python🐍: def permutations(elements): if len(elements) == 0: return [[]] first = elements[0] rest = elements[1:] permsWithoutFirst = permutations(rest) allPermutations = [] for perm in permsWithoutFirst: for i in range(len(perm) + 1): permWithFirst = [*perm[:i], first, *perm[i:]] allPermutations.append(permWithFirst) return allPermutations
Thank you for this video, it is very helpful. Could you show the implementation in java, i could implement the combinations algorithm correctly but for some reason i keep returning an empty list when I change it to permutations
private static Set getAllPossiblePermutationsOfAStringRecursively(String input){ if(input.isEmpty()){ return new HashSet(Collections.singleton(input)); } String firstElement = input.substring(0,1); String remainingElements = input.substring(1); Set permutationsOfRemainingElements = getAllPossiblePermutationsOfAStringRecursively(remainingElements); Set finalPermutations = new HashSet(); for(String s: permutationsOfRemainingElements){ for(int i = 0; i
How it's time Complexity is O(n!)? We have N recursive function calls and in each call we are using nested loop to add current element in all positions. Shouldn't it can be O(n*n!)?
Because they are not nested within each other, you will need to add, not multiply them. So it will be O(n + n!), since its Big Oh, we only consider the worst of the addition, its O(n!)
Incredible explanation , I have this : function permutation(str,prefix,memo=[]) { if (str.length == 0) memo.push(prefix); else{ for(let i = 0; i < str.length ; i++){ let rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str[i] ,memo); } } return memo; }
I'm having trouble grasping how the recursive calls knows to store all permutations in an array. I see that the base case says to return an empty array if/when the array length becomes 0, but until then how does the recursive call know what to return? Where is the data being stored until the callstack is empty and its able to return a final result?
every time there is a recursive call , the current function is paused and stored in memory called stack. This memory is deleted once its recursive call is finished.
Just as Joyce said, each method call and the state is preserved in stack and then retrieved as it returns. Recursion does seem a bit magical sometimes.
Hey, permswithFirst function on line 13 is not getting into my head well ...perm.slice(0, i) - here I understand you are copying all the elements from index 0 to the last i element, firstEl - here you are including the first element, so what does ...perm.slice(i) doing different from ...perm.slice(0, i)
...perm.slice(i) is adding the end of the array to have a complete array with the inserted element. try messing with the single statements code in the console.
Thank you for watching our videos! If you're looking for more interview prep content check out our series on dev.to dev.to/coderbyte/reintroducing-code-review-with-an-interview-question-asked-at-amazon-5a89
@@CoderbyteDevelopers heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
I struggled with the concept until I watched this. The way you combine theory and immediate coding really works for me, thanks. Subscribed!
I've always found permutation algorithms confusing but no one has quite explained it like this. I feel like I'm finally learning. Thank you.
I really enjoy the way you explain. Especially the pace and the simplicity. Thank you so much.
12:38, thanks for further explanation on this. I've learnt algo & ds years ago in college but nothing as clear as a day demo than this! :)
Your lectures are an inspiration to study programming from quite an interesting visual experience. Thanks a ton and please do keep making more of it!
You are my favorite explainer. Great job.
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
// I just saw the recursive tree and implemented it in my way :
const result = [];
function permutation(arr, ans = [], level = 0) {
if (ans.length === arr.length) {
result.push([...ans]);
return;
}
const ele = arr[level]; // element to be placed according to the current level
for (let i = 0; i < ans.length; i++) {
ans.splice(i, 0, ele);
permutation(arr, ans, level + 1)
ans.splice(i, 1);
}
ans.push(ele);
permutation(arr, ans, level + 1);
}
permutation([1, 2, 3]);
console.log(result)
Excellent explanation!!!Thanks a lot Alvin❤
Great explanation! I would recommend slightly better/more unique variable name though
such a clear explanation
great explanation , thanks Alvin
When doing the big O for space, I see you take into account the slice that's on line 5, what about the slices on within the forEach on line 13? do we not take those into account when calculating space?
YOU WERE THE ONE THAT MADE ME understand perm/comb and dp :) I know you did a lot and I just gave you likes and sub BUT I still want to suggest you to do : Backtracking :) thanks
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
Hello Alvin,
Can you please let us know how to further expand the same logic to solve permutation with non unique characters ?
Thanks
create a Memo variable, coderbyte have a excelent explanation too about this implementation in their Dynamic Programming course video th-cam.com/video/oBt53YbR9Kk/w-d-xo.html
@@borisbarzotto5785 heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
@@medazzouzi2649 You are calling the function with rest variable right, so it will return [[2,3], [3,2]]
Sooo clear! Thank you!
Isn't space complexity is also O(n!)? We kind of accumulating all possible permutations (all n! of them). It even might be O(n*n!) since we doing it for each recursive function call
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
For those who use Python🐍:
def permutations(elements):
if len(elements) == 0:
return [[]]
first = elements[0]
rest = elements[1:]
permsWithoutFirst = permutations(rest)
allPermutations = []
for perm in permsWithoutFirst:
for i in range(len(perm) + 1):
permWithFirst = [*perm[:i], first, *perm[i:]]
allPermutations.append(permWithFirst)
return allPermutations
best tutorial of this type problem. go aA
Thank you for this video, it is very helpful. Could you show the implementation in java, i could implement the combinations algorithm correctly but for some reason i keep returning an empty list when I change it to permutations
private static Set getAllPossiblePermutationsOfAStringRecursively(String input){
if(input.isEmpty()){
return new HashSet(Collections.singleton(input));
}
String firstElement = input.substring(0,1);
String remainingElements = input.substring(1);
Set permutationsOfRemainingElements = getAllPossiblePermutationsOfAStringRecursively(remainingElements);
Set finalPermutations = new HashSet();
for(String s: permutationsOfRemainingElements){
for(int i = 0; i
Why though the same code using List instead of Set returns empty list?
How it's time Complexity is O(n!)?
We have N recursive function calls and in each call we are using nested loop to add current element in all positions.
Shouldn't it can be O(n*n!)?
Because they are not nested within each other, you will need to add, not multiply them. So it will be O(n + n!), since its Big Oh, we only consider the worst of the addition, its O(n!)
Incredible explanation , I have this :
function permutation(str,prefix,memo=[]) {
if (str.length == 0)
memo.push(prefix);
else{
for(let i = 0; i < str.length ; i++){
let rem = str.substring(0, i) + str.substring(i + 1);
permutation(rem, prefix + str[i] ,memo);
}
}
return memo;
}
I'm having trouble grasping how the recursive calls knows to store all permutations in an array. I see that the base case says to return an empty array if/when the array length becomes 0, but until then how does the recursive call know what to return? Where is the data being stored until the callstack is empty and its able to return a final result?
every time there is a recursive call , the current function is paused and stored in memory called stack. This memory is deleted once its recursive call is finished.
Just as Joyce said, each method call and the state is preserved in stack and then retrieved as it returns. Recursion does seem a bit magical sometimes.
Hey, permswithFirst function on line 13 is not getting into my head well ...perm.slice(0, i) - here I understand you are copying all the elements from index 0 to the last i element, firstEl - here you are including the first element, so what does ...perm.slice(i) doing different from ...perm.slice(0, i)
...perm.slice(i) is adding the end of the array to have a complete array with the inserted element. try messing with the single statements code in the console.
Nice! Thanks
What about permutations?
Thanks a lot!
Thank you for watching our videos! If you're looking for more interview prep content check out our series on dev.to dev.to/coderbyte/reintroducing-code-review-with-an-interview-question-asked-at-amazon-5a89
@@CoderbyteDevelopers heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
c++ have stl why js don't have standard library for this ?
Awesome
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?
This recursion function is hard to understanding if need to think myself.
cool man 😎
heyy guys please i have trouble with the recursion call let's take an example of input of [1,2,3] for the first recursion call i get that the firstEl =1 ; and the rest varibale [2,3] so we get [1,2,3],[2,1,3,],[2,3,1] then it changes to [1,3,2] how is that possible i mean how do 2 and 3 flip their cases i mean for the second recursion call we only take 3 and the firstEL will be =2 isn't that right ?