0

Heap's algorithm

Please I've been trying to understand this code, I want to use heap algorithm to do permutation. I can't rewrite it in my own way if I don't understand it. I don't know if someone can explain it using the code. Thanks in advance https://code.sololearn.com/cStTCfp0Am9J/?ref=app

25th Mar 2020, 11:46 AM
Joseph Ojo
Joseph Ojo - avatar
3 Answers
+ 3
You need to be familiar with recursion. Each time when the loop begins you call the function until size == 1. Each function call goes into the stack. After that it executes the function call from stack. heapPermutation = hp n is not relevant, so I will leave it away. hp(a, 3) -> calls hp(a, 2) -> calls hp(a, 1) (i is 0) print 1 2 3 now it executes hp(a,2) #i = 0 swap 1 with 2 #2 1 3 restart loop -> call hp(a,1) print 2 1 3 execute hp(a,2) #i = 1 swap 1 with 1 execute hp(a,3) #i = 0 swap 2 with 3 #3 1 2 call hp(a,2) call hp(a,1) print 3 1 2 execute hp(a,2) #i = 0 swap 3 with 1 #1 3 2 restart loop: call hp(a,1) print 1 3 2 execute hp(a,2) #i = 1 swap 3 with 3 execute hp(a,3) #i = 1 swap 1 with 2 #2 3 1 restart loop: call hp(a,2), call hp(a,1) print 2 3 1 execute hp(a,2) #i = 0 swap 2 with 3 #3 2 1 call hp(a,1) print 3 2 1 ... execute the rest (see code in next post)
27th Mar 2020, 8:53 PM
Denise Roßberg
Denise Roßberg - avatar
+ 3
To complete the confusion I have added some print statements for you: https://code.sololearn.com/c63DB00Tg3d1/?ref=app You can also have a look into my java code. Inside the comments you will find some resources. https://code.sololearn.com/cmiKfGRLwLsb/?ref=app I made also a non recursive version: https://code.sololearn.com/co9fPNM638EK/?ref=app
27th Mar 2020, 8:55 PM
Denise Roßberg
Denise Roßberg - avatar
0
Thank you Denise Roßberg, I still find it hard to understand. Maybe a non recursive code will be more explanatory
1st Apr 2020, 2:59 AM
Joseph Ojo
Joseph Ojo - avatar