Permutations generator in Python

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


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

Goran Trlin
Find this and more code examples on:

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:

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

    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.