Author: Goran Trlin

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.