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

Question

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']))

Welcome to Stack Overflow. Don't forget to accept (tick the check-mark next to an answer) and possibly up-vote it when it answers your question, so that your question stops from showing up as unanswered in the searches. — Ivo Mori
– Ivo Mori, Commented Jul 29, 2020 at 4:04
Currently you're asking for someone here to explain the complete algorithm as you have found it – which may be is still too broad. If you can focus your question to some particular part of this iterative implementation of the Heap algorithm then that would be a better question. For example, if your problem is that you don't understand how the c array is used in this implementation then that would be a more specific question. — Ivo Mori
– Ivo Mori, Commented Jul 29, 2020 at 4:16
Also sometimes it can also help to increase ones understanding by "executing" an implementation / algorithm by hand on a piece of paper ;) — Ivo Mori
– Ivo Mori, Commented Jul 29, 2020 at 4:18
@IvoMori Thank you so much for your kind feedback. I am new to Stack Overflow and also programming. I will try my best to keep my questions specific and short next time. — Avy
– Avy, Commented Jul 29, 2020 at 21:25

score 2 · Accepted Answer · 2020-07-30 00:01:13Z

2

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)

edited Jul 30, 2020 at 0:01

answered Jul 29, 2020 at 2:17

user14005715

Sign up to request clarification or add additional context in comments.

13 Comments

Ivo Mori Over a year ago

it works only for numbers: – How so? If you pass in ['a', 'b', 'c'] instead of [1, 2, 3] then you'll get the expected permutations.

Avy Over a year ago

@IvoMori, it works with strings too. You can try it. I tried and it worked for me in the first go.

Avy Over a year ago

@volothud Here is my counter argument – The general definition of combinations is when the order of elements does not matter, for example [1, 2] & [2, 1] are same, a combination of two elements '1' and '2' in each case. But in permutations order does matter, so, [1, 2] & [2, 1] are not same they are two separate things. Even in Itertools you can set a length to the permutations >>> print list(permutations('abc', 2)) will give you following output [('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]. I am trying to achieve the same with Heap's algorithm not Itertools.

user14005715 Over a year ago

@Avy Updated the code. Is this what you want? (It seems that this is what itertools is doing, judging by the result.)

user14005715 Over a year ago

Just to clarify: limiting the result length like this, will not give real combinations; just truncated permutations.

|

Collectives™ on Stack Overflow

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

1 Answer 1

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related