Heap's algorithm

Question

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

Answer 1

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)

Answer 2

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

Answer 3

Thank you Denise Roßberg, I still find it hard to understand.

Maybe a non recursive code will be more explanatory