CODEWITHSUNDEEP
pythonstringpermutationnon-recursiveheaps-algorithm
Jahleel Murray
Jahleel Murray

Reputation: 1

Trying to understand this non-recursive Heap's Permutation Algorithm

Right now I'm trying to understand why a certain non-recursive implementation of the Heap's Permutation Algorithm works. I implemented some code of this particular version of the algorithm in python, but I don't understand the logic behind what makes it work.

def element_swap(str_list, i1, i2):
    last = str_list[i1]
    last_swapee = str_list[i2]
    str_list[i1] = last_swapee
    str_list[i2] = last

def theRealPermuator(str_input):
    generated_permutations = [str_input]
    permute_this = list(str_input)
    length = len(permute_this)
    c = [0 for i in range(length)]
    i = 0
    while i < length:
        if c[i] < i:
            if i%2 == 0:
                element_swap(permute_this, 0, i)
            else:
                element_swap(permute_this, c[i], i)
            generated_permutations.append(''.join(permute_this))
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return generated_permutations



print(theRealPermuator('ABC'))

Output: ['ABC', 'BAC', 'CAB', 'ACB', 'BCA', 'CBA']

I implemented the python code from the algorithm listed at this site: https://www.baeldung.com/cs/array-generate-all-permutations (see: 4.2. Non-Recursive Heap’s Algorithm)

Would anyone be able to explain the logic behind how this code generates the Output?

Upvotes: 0

Views: 86

Answers (0)

Related Questions