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
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)
+ 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
0
Thank you Denise RoĂberg, I still find it hard to understand.
Maybe a non recursive code will be more explanatory