Heap's Algorithm in JavaScript - Get All The Permutations of an Array
Вставка
- Опубліковано 11 жов 2024
- In this video we will learn what permutations are and recreate Heap's Algorithm in Javascript. This is a function where, given an array of elements, it will give you all the permutation of the array. Learn this and level up your coding interview skills!
🗄 Resources:
Finished Code: gist.github.co...
Wikipedia Article: en.wikipedia.o...
🔑 Key Concepts:
Permutations
Recursion
Pure Function
#Algorithm #Permutations #JavaScript
thank you so much for the video !!! i really appreciate this and for ppl who wants break down in the text here is my break down based on justin's video
- g(3, [1, 2, 3])
- g(2, [1, 2, 3])
- g(1, [1, 2, 3])
- **Base case**: Push `[1, 2, 3]` to output
- g(2, [1, 2, 3]) // First iteration of the loop
- N === 2, so we swap [1, 2, 3] to [2, 1, 3]
- g(1, [2, 1, 3])
- **Base case**: Push `[2, 1, 3]` to output
- g(3, [1, 2, 3]) // Second iteration of the loop
- N === 3, swap [2, 1, 3] to [3, 1, 2]
- g(2, [3, 1, 2])
- g(1, [3, 1, 2])
- **Base case**: Push `[3, 1, 2]` to output
- N === 2, swap [3, 1, 2] to [1, 3, 2]
- g(1, [1, 3, 2])
- **Base case**: Push `[1, 3, 2]` to output
- g(3, [1, 2, 3]) // Third iteration of the loop
- N === 3, swap [1, 3, 2] to [2, 3, 1]
- g(2, [2, 3, 1])
- g(1, [2, 3, 1])
- **Base case**: Push `[2, 3, 1]` to output
- N === 2, swap [2, 3, 1] to [3, 2, 1]
- g(1, [3, 2, 1])
- **Base case**: Push `[3, 2, 1]` to output
after 10 videos on this subject, I finally kind of understand
dude. yes. this is the JS algos channel i've been looking for lol. just earned a subscriber
Finally, someone explaining it who understands it. So many people act confident but then when it comes to the actual tricky part, they don't explain. Fantastic work.
Delighted to see such a lucid explanation of a complex algorithm. I just started getting familiar with recursion and stumbled across a permutation problem with Heap's algorithm. The explanation here is as simple as it can get. Thank you for this video.
OMG in Discrete Math, the number of permutations looks kinda easy to grasp, but I've never expected to list them one by one needs such a delicate and clever algo. Thank you for your explanation.
This problem was so complicated. I saw a few explanations but this was the best one yet. The other explanations were in other languages as well so it was hard to follow. Yours was very clear with good examples. Please do more
Nice Explanation on Heap Algorithm. All students must watch. Thank you for your time
and good health.
thanks for your kind words!
Finally after watching a bunch of videos, this was the only one that made me understand this craziness... just earned a subscriber!
This video saved my life, thank you!
that was literally just brilliant, I got stuck at one point tho. The keyword 'return' after 'output.push' gives back the newly re-arranged array to the previous function to enter the for loop. I know you've mentioned it briefly in the explanation, but hope this helps anyone who attempt it and got stuck prior watching your explanation! I wonder tho if anyone knows whether this alogrithm relates to the principle of "fist in last out" as that seemed to be how each generate function gets slotted and executed?
2:15 "We go inside this crazy for lop" HAHAHAHA
sir Kim this is educational for new comers
Awesome video, I hadn't seen recursion so well explained before :)
great job, excellent!
Awesome men !!!!
Awesome. But what happens when you have 30 elements... Call stack?
Excellent video. I think is the easiest to understand
Thanks Brother
wow that was a pretty good tutorial
I dont understand how the swapped version of the array persists even after that specific function is closed out. after you make 123 into 213 and push it into the array, you go back to the original call. shouldn't that call still have the original array as 123 ? so it would change to 312 first (0 index and second index)?
I have a question at 2:57, maybe you will cover it later. If I have an array of 1,2,3,4,5 and I also want to include combinations such as 111 or 121? How come they aren't considered possible combinations here? I'm really new at this, sorry if this is a stupid question. :)
Why does it passes the 17th line when n = 1, instead of simply returning from the function?
Is there any way to find all of the strings that are 4 in length with letters A-Z and numbers 0-9?
Great explanation :)
Is there a way to do this where I can control the site of the sets? For example, have them get in sets of three.
Could you give practical use cases for such an algorithm?
Good question! I initially made this video because I needed this algorithm for this FCC algorithm question: www.freecodecamp.org/learn/coding-interview-prep/algorithms/no-repeats-please
However, that doesn't really answer your question for it being a 'practical use case'. I think a more practical use case would involve any application wherein you need all the permutations of said data. For example, let's say you made a survey where you rank certain items in an order, and for whatever reason you wanted to keep track of all the permutations of that order.
i dont think it could be easy to come up with practical cases. all i know it is good for study sir.
I needed this algorithm when I wanted to write a brute force search through all the permutations.
Is this the right arrangement? Nope.
Is this the right arrangement? Nope.
Is this the right arrangement? Nope.
Is this the right arrangement? Nope.
Is this the right arrangement? Nope.
Is this the right arrangement? ...
An Anagram solver.
Amazing video. How do I handle duplicate permutations here?
You could use a javascript set or map to store the output values. Thatll only store unique permutations
May I know, what vs code extension did you use to for a symbol like =>, ====, !== gives such a user-friendly symbol?
Thx a million!!!
#NoWords!
😘
Hi, what do I need to change or add if I want only 8 number combinations out of 25 number array
O man thank you
Thanks
How did this guy Heap come up with this?? lol thanks for the vid tho
What about this?
// Return all possible combination in an array
//
function getPermutations(inputArray) {
var permutationsArr = []
function getPermitationsRecursively(destArray, baseArray) {
let lengthBase = baseArray.length,
permute;
for (let i = 0; i < lengthBase; i++) {
permute = [...destArray],
base = [...baseArray]
permute.push(base[i])
base.splice(i,1)
if(base.length > 0){
getPermitationsRecursively(permute, base)
} else {
permutationsArr.push(permute)
}
}
return permutationsArr
}
return getPermitationsRecursively([], inputArray)
}
Could you tell me how I can use this algorithm with fixed length? For example, I want all the permutations with 3 length from [1,2,3,4,5,6,7,8,9,10]. Sometime like [12,3] [1,24,] [1,2,5].....ect
Yes!!!
There are this solution (if omit lengthLimit works like the video)
function getPermutations(inputArray, lengthLimit) {
var permutationsArr = []
function getPermitationsRecursively(destArray, baseArray) {
let lengthBase = baseArray.length,
base, permutation;
for (let i = 0; i < lengthBase; i++) {
permutation = [...destArray],
base = [...baseArray]
permutation.push(base[i])
base.splice(i,1)
if(base.length > (inputArray.length - lengthLimit | 0)){
getPermitationsRecursively(permutation, base)
} else {
permutationsArr.push(permutation)
}
}
return permutationsArr
}
return getPermitationsRecursively([], inputArray)
}
var permutations = getPermutations([1,2,3,4,5,6,7,8,9,10], 3)
console.log(permutations)
// return 720 possible permutations
Tell me if it works to you. Bye
what if the numbers are repeated?
The index is swapped and it doesn't care what the values are
You wouldn't need Heap's or anything like it. You could simply iterate each element in a loop. For [1,2,3] you'd just start with the first element in all positions. [1,1,1], then loop each position with all the digits. Heap's is used when you need to be efficient due to a large-sized array being permuted. By simply looping through without the crazy swapping that Heap's does, you end up with magnitudes more work being done be the CPU. For example, if you want to make all of the solvable Sudoku boards it would take many computers years if done perfectly, and lifetimes if done with simple iteration.
19:32
arrToSwap[indexB], arrToSwap[indexA] = arrToSwap[indexA], arrtoSwap[indexB];
Oooooh! I dislike recursive programming...I don't find it intuitive at all. This video is very helpful for understanding it, though.