DEV Community

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

Posted on

2 2

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

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs