Permutations generator in Python

This is a small Python program for generating permutations from an integer array provided as input. The output format is an array of integer arrays.

The core ideas behind this solution:

• Backtracking is used to completely traverse the search space
• Search space gets smaller with every new layer of the recursive call
• Each new layer of recursion creates a set of additional arrays
• Once the search space is exhausted, the recursion stops and the accumulated array gets added to the final output

Code:

'''
Simple permutations generator example in Python
Generates permutations of an integer array provided as the parameter of permute() method

Author:
Goran Trlin
Find this and more code examples on:
https://playandlearntocode.com

'''
class PermutationsGenerator:
all_permutations = []

def _backtrack(self, cur_arr, search_space):
'''
Loop over the remaining search space, and add every element to the beginning of a new branch:
'''
if len(search_space) == 0:
# the cur_arr is now full so we can add this combination to the output queue:
self.all_permutations.append(cur_arr)
return

for i in range(len(search_space)):
# contactenate the rest of the elements into the new search_space
self._backtrack(cur_arr[:] + [search_space[i]], search_space[:i] + search_space[i + 1:])
return

def permute(self, nums):
self.all_permutations = []

# start by adding N branches as the starting points:
for i in range(len(nums)):
self._backtrack([nums[i]], nums[:i] + nums[i + 1:])

return self.all_permutations



The code for this project can be found on GitHub.