pythonalgorithmpermutationheaps-algorithm

Heap's Algorithm - Non Recursive Method in Python to generate permutations


I am a newbie to programming. I am working on Heap's Algorithm, specifically non-recursive method. There is not so much explanation available on internet, to how the algorithm works. I found this piece of work from Bernardo Sulzbach but he doesn't explain how his algorithm works. I am stuck on it from days, tried everything couldn't figure it out. I have added comments after each line to make myself understand -- what's happening here? but I still couldn't make it work. Am I doing something wrong? Please help.

# Heap's Algorithm (Non Recursive)

# function to swap values in python
def swap(elements, i, j):
    elements[i], elements[j] = elements[j], elements[i]

# function to generate permutation
def generate_permutations(elements, n): 
    # Passing two parameters of elements and n to function "generate_permutations".
    c = [0] * n 
    # c is a new list and its value set to an array literal with value 0, n times.
    # Example - [a] * 3 ==> ['a', 'a', 'a', 'a']
    yield elements 
    # "yield" statement is used to define generators, while "return" statement causes a function to exit.
    # "yield" replacing the return of a function to provide a result to its caller without destroying
    # local variables. Unlike a function, where on each call it starts with new sets of variables, a generator
    # will resume the execution where it left off.
    i = 0
    # i is a new variable and its value is set to 0. It can also be used to count the number of loop runs.
    while i < n:
    # while loop ==> while i is less than n, do following:
        if c[i] < i:
        # if statement ==> while i is less than n and if any element from 'c' list is less than i, 
        # then do following:
            if i % 2 == 0:
            # if statement ==> while i is less than n, and if any element in 'c' list is less than i, and
            # i is an even number, then do following:
                swap(elements, 0, i)
                # calling swap function and passing following arguments: elements, '0' and 'i'
            else:
            # else, if all three conditions above are not true then do following:
                swap(elements, c[i], i)
                # calling swap funtions and passing following arguments: elements, an item from 'c' list and 'i'
            yield elements
            # ??? yield elements
            c[i] += 1
            # after that, increment c[i] by 1.
            i = 0
            # set the value of i to 0
        else:
            # else, if c[i] < i is not true the do the following.
            c[i] = 0
            # set the value of c[i] to 0
            i += 1
            # and increment i by 1

def permutations(elements):
    return generate_permutations(elements, len(elements))

# Driver Code
# c = ?
# n = ?
# i = ?
print(permutations(['abc']))

Solution

  • Just cleaning up your code (too many comments):

    # Heap's Algorithm (Non Recursive)
    # https://en.wikipedia.org/wiki/Heap%27s_algorithm
    
    def swap(seq, i, j):
      seq[i], seq[j] = seq[j], seq[i]
    
    def generate_permutations(seq, seqLen, resLen): 
      c = [0] * seqLen
      yield seq[:resLen]
      
      i = 0
      while i < seqLen:
        if c[i] < i:
          if i % 2 == 0:
            swap(seq, 0, i)
          else:
            swap(seq, c[i], i)
          yield seq[:resLen]
          c[i] += 1
          i = 0
        else:
          c[i] = 0
          i += 1
    
    def permutations(seq, resLen=None):
      if not resLen: resLen = len(seq)
      return generate_permutations(seq, len(seq), resLen)
    
    for p in permutations([1,2,3]): print(p)
    for p in permutations([1,2,3],2): print(p)