Permutations

This story elaborates how to generate next permutation in lexicographic order and then uses the same approach to generate all the permutations of the given array which contains either distinct or duplicate values.

permutations summary card

Table of Contents
· Permutations
· Lexicographic Permutation Order
· Next Permutation
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python
· Permutations(distinct or duplicates values)
  ∘ Graphical Explanation
  ∘ Code Implementation
    ∘ Complexity
    ∘ Golang
    ∘ Python

Permutations

Given n distinct items, the number of permutations is n factorial(n!). When we pick the first item from the n items, the remaining n-1 items are for the second pick. Likewise, n-2 items are remaining for third pick and so on.

n x (n-1) x (n-2) x ... x 2 x 1 = n!

permutations

Order does matter when we have a permutation.

Lexicographic Permutation Order

{1, 2, 3}

Permutations in lexicographic order:

1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 1, 2}
6. {3, 2, 1}

The smallest permutation of {1, 2, 3} is {1, 2, 3} and the largest permutation is {3, 2, 1}.

Next Permutation

LeetCode 31: Next Permutation

The idea is to find the longest decreasing sequence and identify the first non-decreasing element. Then traverse backward to find the first element that is greater than the first non-decreasing element and swap them. Finally reveres the longest decreasing sequence to minimize the permutation.

next permutation approach

If the given array is in decreasing order, it is the largest permutation. Reverse the array to return the smallest permutation.

edge case

Graphical Explanation

• step1: traverse backward to find the longest decreasing sequence

array[i-1] >= array[i]

• step2: identify the first non-decreasing element

array[i-1] < array[i]

• step3: traverse backward to find the first element greater than the first non-decreasing element

array[j] > array[firstNonDecreasingElement]

• step4: swap the first non-decreasing element and the first element greater than it

array[j], array[firstNonDecreasingElement] = array[firstNonDecreasingElement], array[j]

• step5: reverse the longest decreasing sequence

process 1

process 2

Code Implementation

Complexity

Time: O(n)
Space: O(1) The next permutation is generated in-place
n: the total number of elements in the given array

Golang

Python

Permutations(distinct or duplicates values)

LeetCode 46: Permutations
LeetCode 47: Permutations II

Generate all permutations in lexicographic order until the permutation is equal to the original array.

This approach can handle either distinct or duplicate values in the given array because it can generate all possible unique permutations.

Graphical Explanation

permutation process

Code Implementation

Complexity

Time: O(n*n!)

O(n): n iterations required to find the next permutation
O(n!): n! permutations

Space: O(n*n!)

O(n): each permutation contains n elements
O(n!): n! permutations

n: the total number of elements in the given array

Golang

Python

You can access the source code here.

LeetCode Problems:

• LeetCode 31: Next Permutation
• LeetCode 46: Permutations
• LeetCode 47: Permutations II