Search
 
SCRIPT & CODE EXAMPLE
 
CODE EXAMPLE FOR PYTHON

permutations of a set

"""
This implementation demonstrates how 
to generate all the permutations of 
a given set of integers.

Example: 
For following array: [1, 2, 3]
The output would be: 
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], 
[3, 1, 2], [3, 2, 1]]

Let n be the size of the array.

Time complexity: O(n*n!)
Space complexity: O(n*n!)
"""


def find_permutations(array):
    permutations = []
    generate_permutations(0, array, permutations)
    return permutations


def generate_permutations(idx, array, permutations):
    if idx == len(array) - 1:
        permutations.append(array[:])  # add a copy of array to output
    else:
        for j in range(idx, len(array)):
            swap(array, idx, j)  # swap idxth elem with every other elem
            generate_permutations(idx+1, array, permutations)
            swap(array, j, idx)  # backtrack


def swap(array, i, j):
    array[i], array[j] = array[j], array[i]


# Below outputs:
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
print(find_permutations([1, 2, 3]))

"""
# Another solution:
import itertools
# Below output:
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
print(list(itertools.permutations([1, 2, 3])))
"""
 
PREVIOUS NEXT
Tagged: #permutations #set
ADD COMMENT
Topic
Name
6+7 =