Next Permutation of Array in DSA Python - Deep Dive

Overview - Next Permutation of Array

What is it?

Next Permutation of Array is a way to rearrange numbers in an array to get the next bigger arrangement in order. If the array is already the biggest possible order, it resets to the smallest order. This helps find the next sequence without listing all permutations. It works by changing the array in place with a few simple steps.

Why it matters

Without next permutation, finding the next bigger arrangement would mean generating all possible orders, which is slow and uses a lot of memory. This method lets programs quickly jump to the next order, useful in puzzles, sorting tasks, and algorithms that explore options step-by-step. It saves time and makes complex problems easier to solve.

Where it fits

Before learning this, you should understand arrays and how to compare sequences. After this, you can explore full permutation generation, backtracking algorithms, and combinatorial problems that use permutations to find solutions.

Mental Model

Core Idea

Next permutation finds the next bigger arrangement by changing the array from right to left, swapping and reversing parts to get the smallest bigger order.

Think of it like...

Imagine you have a row of books sorted by height. To find the next taller arrangement, you look from right to left to find the first book that can be swapped with a taller one on its right, then reorder the books after it to be as short as possible.

Array: [1, 2, 3, 6, 5, 4]
Step 1: Find pivot (from right, first decrease): 3 at index 2
Step 2: Find successor (just bigger than pivot): 4 at index 5
Step 3: Swap pivot and successor: [1, 2, 4, 6, 5, 3]
Step 4: Reverse suffix after pivot: [1, 2, 4, 3, 5, 6]

Build-Up - 7 Steps

1

Foundation

Understanding permutations and order

Concept: What permutations are and how arrays can be ordered.

A permutation is a way to arrange items in order. For example, [1, 2, 3] can be arranged as [1, 3, 2], [2, 1, 3], etc. These arrangements can be sorted from smallest to largest based on number order. Understanding this order helps us find the next arrangement after any given one.

Result

You know that permutations can be ordered and that 'next' means the next bigger arrangement in this order.

Understanding the order of permutations is key to knowing what 'next' means and why we want to find it efficiently.

2

Foundation

Identifying the pivot in the array

Concept: Finding the first place from the right where the order decreases.

Look at the array from right to left. Find the first element that is smaller than the one after it. This element is called the pivot. For example, in [1, 2, 3, 6, 5, 4], starting from the right: 5 > 4 (no), 6 > 5 (no), 3 < 6 (yes), so pivot is 3 at index 2.

Result

You can find the pivot index where the next permutation change starts.

Finding the pivot tells us where the array stops increasing from the right, marking the place to change for the next bigger order.

3

Intermediate

Finding the successor to swap with pivot

🤔Before reading on: do you think the successor is the smallest or largest number bigger than the pivot? Commit to your answer.

Concept: Find the smallest number bigger than the pivot to the right of it.

After finding the pivot, look to the right side of the array to find the smallest number that is bigger than the pivot. This is the successor. For example, pivot=3, numbers to right are [6,5,4]. The smallest bigger than 3 is 4.

Result

You identify the correct number to swap with the pivot to get the next bigger arrangement.

Choosing the smallest bigger number ensures the next permutation is just one step bigger, not skipping any arrangements.

4

Intermediate

Swapping pivot and successor

Concept: Exchange the pivot and successor to move to the next bigger order.

Swap the pivot element with the successor found. For example, swap 3 and 4 in [1, 2, 3, 6, 5, 4] to get [1, 2, 4, 6, 5, 3]. This moves the array closer to the next permutation.

Result

The array now has a bigger prefix, but the suffix might still be unordered.

Swapping moves the pivot to a bigger value, but the rest needs reordering to get the smallest bigger permutation.

5

Intermediate

Reversing the suffix after pivot

Concept: Reverse the part of the array after the pivot to get the smallest order.

After swapping, reverse the part of the array to the right of the pivot index. This makes the suffix the smallest possible order. For example, reverse [6, 5, 3] to [3, 5, 6], resulting in [1, 2, 4, 3, 5, 6].

Result

The array is now the next permutation in order.

Reversing ensures the suffix is the smallest arrangement, so the whole array is the immediate next bigger permutation.

6

Advanced

Handling the highest permutation case

🤔Before reading on: if the array is in descending order, do you think next permutation exists or resets? Commit to your answer.

Concept: If the array is the biggest order, reset to smallest order by reversing whole array.

If no pivot is found (array is descending), it means the array is the highest permutation. The next permutation is the smallest one, so reverse the entire array. For example, [3, 2, 1] reversed to [1, 2, 3].

Result

The array resets to the smallest order, ready to start over.

Knowing when to reset prevents errors and completes the cycle of permutations.

7

Expert

In-place algorithm and time complexity

🤔Before reading on: do you think next permutation requires extra memory or can be done in-place? Commit to your answer.

Concept: Next permutation can be done in-place with O(n) time and O(1) extra space.

The algorithm only swaps and reverses parts of the original array without extra arrays. It scans from right to left once or twice, so time is linear in array size. This makes it efficient for large arrays and real-time use.

Result

You understand the algorithm is memory efficient and fast.

Knowing the algorithm is in-place and linear time helps choose it for performance-critical tasks.

Under the Hood

The algorithm scans the array from right to left to find the pivot where the order breaks ascending. Then it finds the successor just bigger than the pivot to swap. After swapping, it reverses the suffix to get the smallest order. This works because permutations are ordered lexicographically, and these steps move to the next lex order.

Why designed this way?

This method was designed to avoid generating all permutations, which is costly. It uses the property of lexicographic order to jump directly to the next permutation. Alternatives like generating all permutations or brute force sorting are slower and use more memory.

Array: [a0, a1, ..., apivot, ..., an-1]

Step 1: Find pivot p where a[p] < a[p+1]
  ↓
Step 2: Find successor s > a[p] in suffix
  ↓
Step 3: Swap a[p] and a[s]
  ↓
Step 4: Reverse suffix from p+1 to end
  ↓
Result: Next permutation in lex order

Myth Busters - 4 Common Misconceptions

Quick: Does next permutation always increase the first element? Commit yes or no.

Common Belief: Next permutation always changes the first element of the array.

Reality: Next permutation changes the rightmost pivot element, which may not be the first element.

Why it matters: Assuming the first element always changes leads to wrong implementations and missed edge cases.

Quick: Is reversing the suffix after swapping optional? Commit yes or no.

Common Belief: After swapping pivot and successor, the suffix order does not matter.

Reality: Reversing the suffix is necessary to get the smallest order and ensure the next permutation is immediate.

Why it matters: Skipping reversal can produce a permutation that is bigger but not the next immediate one, breaking correctness.

Quick: If the array is descending, does next permutation not exist? Commit yes or no.

Common Belief: If the array is in descending order, there is no next permutation.

Reality: If descending, the next permutation is the smallest order, which is the array reversed (ascending).

Why it matters: Not resetting leads to errors or infinite loops in algorithms that cycle through permutations.

Quick: Does next permutation require extra memory proportional to array size? Commit yes or no.

Common Belief: Next permutation needs extra arrays or memory to store permutations.

Reality: Next permutation works in-place with constant extra memory.

Why it matters: Thinking extra memory is needed can prevent using this efficient method in memory-sensitive applications.

Expert Zone

1

The pivot is always the rightmost element where ascending order breaks, ensuring minimal change to get next permutation.

2

Reversing the suffix is equivalent to sorting it because the suffix is always in descending order before reversal.

3

In some languages or contexts, careful index handling is needed to avoid off-by-one errors in pivot and successor selection.

When NOT to use

Next permutation is not suitable when you need all permutations or random permutations. For generating all permutations, backtracking or Heap's algorithm is better. For random permutations, use shuffle algorithms like Fisher-Yates.

Production Patterns

Used in combinatorial optimization, generating next states in search algorithms, solving puzzles like the traveling salesman problem, and in coding interviews to test understanding of permutations and array manipulation.

Connections

Lexicographic Order

Next permutation builds on lexicographic ordering of sequences.

Understanding lexicographic order clarifies why the algorithm finds the next bigger arrangement by minimal changes.

Backtracking Algorithms

Next permutation can be used to generate next candidate states in backtracking.

Knowing next permutation helps efficiently explore solution spaces without generating all permutations upfront.

Music Composition Patterns

Both next permutation and musical note sequences explore ordered arrangements with constraints.

Recognizing patterns in music composition can inspire understanding of ordered arrangements and transitions like next permutation.

Common Pitfalls

#1 Not reversing the suffix after swapping pivot and successor.

Wrong approach:

def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i >= 0:
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
# Missing reversal here
return arr

Correct approach:

def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i >= 0:
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1:] = reversed(arr[i + 1:])
return arr

Root cause:

Misunderstanding that swapping alone is enough without reordering the suffix.

#2 Assuming next permutation always changes the first element.

Wrong approach:

def next_permutation(arr):
# Always swap first element with next bigger
for i in range(1, len(arr)):
if arr[i] > arr[0]:
arr[0], arr[i] = arr[i], arr[0]
break
return arr

Correct approach:

def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i >= 0:
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1:] = reversed(arr[i + 1:])
return arr

Root cause:

Not understanding the pivot concept and lexicographic order.

#3 Not handling the case when array is in descending order.

Wrong approach:

def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i < 0:
return arr # No change for highest permutation
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1:] = reversed(arr[i + 1:])
return arr

Correct approach:

def next_permutation(arr):
i = len(arr) - 2
while i >= 0 and arr[i] >= arr[i + 1]:
i -= 1
if i < 0:
arr.reverse()
return arr
j = len(arr) - 1
while arr[j] <= arr[i]:
j -= 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1:] = reversed(arr[i + 1:])
return arr

Root cause:

Ignoring the reset step for the highest permutation case.

Key Takeaways

Next permutation finds the immediate next bigger arrangement of an array in lexicographic order by changing it in place.

The algorithm works by finding a pivot from the right where the order decreases, swapping it with the smallest bigger successor, then reversing the suffix.

If the array is the highest permutation (descending order), the next permutation resets it to the smallest order by reversing the whole array.

This method is efficient, using O(n) time and O(1) extra space, making it practical for large arrays and real-time applications.

Understanding next permutation helps in solving combinatorial problems, optimizing search algorithms, and mastering array manipulation techniques.