0

I am trying to generate all the permutations of a given set through recursion. Idea is that function will iterate through all the elements of the provided set, append each element to a local output list while simultaneously modifying the set by removing that element as long as set is not empty. Once set becomes empty, function appends local output list to a master list and then go back to the execution context to iterate through remaining elements. This approach is summarized in figure below -

Recursion tree image from YouTube channel 'Time Complexity Infinity'

I have written following code in python-

master_output = []
output = []
def PermTree(set):
    for element in set:
        if bool(set) is False:
            master_output.append(output)
        else:
            output.append(element)
            set.remove(element)
            PermTree(set)
        output.pop()
    return master_output
result = PermTree([1, 2, 3])
print(result)

This function can go through first few iterations but when the set becomes empty, it quits. For e.g. in a given set of [1, 2, 3], it will go as follows -

PermTree([1, 2, 3])
# set not empty > append element to output
output = [1]
# remove element from set
set = [2, 3]
# recursive call to PermTree()
PermTree([2, 3])
# set not empty > append element to output
output = [1, 2]
# remove element from set
set = [3]
# recursive call to PermTree()
PermTree([3])
# set not empty > append element to output
output = [1, 2, 3]
# remove element from set
set = []
# recursive call to PermTree()
PermTree([])

This function quits here as set has become empty (if block doesn't execute). What I would like is that function doesn't quit here and instead append output to master output and then pop() the output and then go to the next iteration. That is -

PermTree([])
# set empty > append output to master output
# pop() the output
output = [1, 2]
# go to next iteration
PermTree([3])
# element has already been iterated
# pop() the output
output = [1]
# go to next iteration
PermTree([2, 3])
# set not empty > append element ('3') to output ('2' was covered in first iteration)
output = [1, 3]
# remove element from set
set = [2]
# ... and so on..

Any suggestion on how to get my code working would be appreciated .I am new to python, so any other syntax improvement suggestions will also be helpful.

Gurjot Singh Sidhu
  • 3
  • 4
  • You need `return` before the recursive call: `return PermTree(set)` – Barmar Sep 14 '21 at 16:59
  • BTW, don't use `set` as a variable name, it shadows the built-in function. – Barmar Sep 14 '21 at 17:00
  • Thanks Barmar for your comments, but adding return before recursive call didn't solve my problem. Function still quits when it sees an empty set as input. – Gurjot Singh Sidhu Sep 14 '21 at 17:33
  • Isn't an empty set the base case of the recursion? What should it do if there's nothing to iterate over? – Barmar Sep 14 '21 at 18:59
  • You should put `if bool(set) is False:` outside the loop. – Barmar Sep 14 '21 at 19:00
  • And it's more pythonic to write `if len(set) == 0:` or `if not set:` – Barmar Sep 14 '21 at 19:00
  • Using `if bool(set) is False:` outside the loop still doesn't work. When I used input set as [1,2,3] as input set it gave me a traceback instead of the desired **master output** list - [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. – Gurjot Singh Sidhu Sep 14 '21 at 20:01
  • Another problem here: You are modifying a collection _while at the same time iterating over it_. That's generally a recipe for disaster. Or at the very least a recipe for wrong outcomes. – cadolphs Sep 14 '21 at 20:11

0 Answers0