DEV Community

Cover image for Today I Learned: Permutations
Anzhari Purnomo
Anzhari Purnomo

Posted on

Today I Learned: Permutations

Problem Statement

Write a function that takes in an array of unique integers and then returns an array of all unordered permutations.

Sample Input

array = [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

Sample Result

[
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
]
Enter fullscreen mode Exit fullscreen mode

Code #1

def get_permutations(array):
    permutations = []
    helper(0, array, permutations)
    return permutations


def helper(i, array, permutations):
    if i == len(array) - 1:
        permutations.append(list(array))
    else:
        for j in range(i, len(array)):
            swap(array, i, j)
            helper(i + 1, array, permutations)
            swap(array, i, j)


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

Enter fullscreen mode Exit fullscreen mode

Notes

  • Assumption: if the input array is empty, return empty array.
  • Try thinking of permutations as a graph.
  • TODO: try the iterative approach.

Credits

Top comments (0)