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.

Practice

1. What does the next permutation of an array represent?

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

Solution

1. Step 1: Understand the concept of permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation meaning

   The next permutation is the next arrangement that is just greater than the current one in this order.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option A

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Next permutation means next bigger order arrangement [OK]

Common Mistakes:

• Thinking next permutation is just sorting ascending
• Confusing next permutation with reversing the array
• Assuming next permutation always moves smallest element front

2. Which of the following Python code snippets correctly swaps two elements arr[i] and arr[j] in an array?

easy

A. arr[i], arr[j] = arr[j], arr[i]

B. arr[i] = arr[j]; arr[j] = arr[i]

C. swap(arr[i], arr[j])

D. arr[i] = arr[j]

Solution

1. Step 1: Recall Python tuple unpacking for swapping

   Python allows swapping two variables in one line using tuple unpacking.

2. Step 2: Check each option

   arr[i], arr[j] = arr[j], arr[i] correctly swaps using arr[i], arr[j] = arr[j], arr[i]. arr[i] = arr[j]; arr[j] = arr[i] overwrites arr[i] before assigning arr[j]. swap(arr[i], arr[j]) is invalid syntax without a defined function. arr[i] = arr[j] only assigns one element.

3. Final Answer:

   arr[i], arr[j] = arr[j], arr[i] -> Option A

4. Quick Check:

   Python swap uses tuple unpacking [OK]

Hint: Use tuple unpacking to swap in Python [OK]

Common Mistakes:

• Overwriting one element before swapping
• Using undefined swap function
• Assigning only one element instead of both

3. What is the output of the following code snippet?

arr = [1, 3, 2]
# Apply next permutation logic
# Step 1: Find first decreasing element from right (index 0)
# Step 2: Find element just larger than arr[0] from right (index 2)
# Step 3: Swap arr[0] and arr[2]
# Step 4: Reverse elements after index 0

arr[0], arr[2] = arr[2], arr[0]
arr[1:] = arr[1:][::-1]
print(arr)

medium

A. [3, 1, 2]

B. [2, 1, 3]

C. [1, 2, 3]

D. [2, 3, 1]

Solution

1. Step 1: Identify the first decreasing element from right

   From right, arr[1]=3 > arr[2]=2 (not decreasing), arr[0]=1 < arr[1]=3 (decreasing at index 0)

2. Step 2: Find element just larger than arr[0] from right

   From right, arr[2]=2 > arr[0]=1, so index 2 chosen

3. Step 3: Swap arr[0] and arr[2]

   Swap 1 and 2 -> arr becomes [2, 3, 1]

4. Step 4: Reverse elements after index 0

   Reverse arr[1:] -> arr[1:] = [3,1] reversed to [1,3]

5. Final Answer:

   [2, 1, 3] -> Option B

6. Quick Check:

   Next permutation of [1,3,2] = [2,1,3] [OK]

Hint: Swap pivot with next bigger, then reverse suffix [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping wrong elements
• Confusing increasing and decreasing order

4. The following code attempts to find the next permutation of arr = [3, 2, 1]. What is the error?

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:])

arr = [3, 2, 1]
next_permutation(arr)
print(arr)

medium

A. The while loop condition is incorrect

B. Swapping elements is done in wrong order

C. Using reversed() returns an iterator, not a list, causing wrong assignment

D. The function does not handle empty arrays

Solution

1. Step 1: Analyze the reversal line

   The line arr[i + 1:] = reversed(arr[i + 1:]) assigns an iterator to a list slice, which expects a list.

2. Step 2: Identify correct usage

   To assign reversed elements properly, convert iterator to list: arr[i + 1:] = list(reversed(arr[i + 1:])).

3. Final Answer:

   Using reversed() returns an iterator, not a list, causing wrong assignment -> Option C

4. Quick Check:

   reversed() needs list() for slice assignment [OK]

Hint: Use list(reversed(...)) when assigning slices [OK]

Common Mistakes:

• Assigning reversed() iterator directly to list slice
• Ignoring empty array edge case
• Swapping elements incorrectly

5. Given the array arr = [1, 5, 1], what is the next permutation after applying the standard algorithm? Consider duplicates carefully.

hard

A. [5, 1, 5]

B. [1, 1, 5]

C. [1, 5, 1]

D. [5, 1, 1]

Solution

1. Step 1: Find first decreasing element from right

   From right: arr[1]=5 > arr[2]=1 (not decreasing), arr[0]=1 < arr[1]=5 (decreasing at index 0)

2. Step 2: Find element just larger than arr[0] from right

   From right, arr[2]=1 not > 1, arr[1]=5 > 1, so index 1 chosen

3. Step 3: Swap arr[0] and arr[1]

   Swap 1 and 5 -> arr becomes [5, 1, 1]

4. Step 4: Reverse elements after index 0

   Reverse arr[1:] -> arr[1:] = [1,1] reversed is same [1,1]

5. Final Answer:

   [5, 1, 1] -> Option D

6. Quick Check:

   Duplicates handled, next permutation = [5,1,1] [OK]

Hint: Swap pivot with next bigger, reverse suffix even with duplicates [OK]

Common Mistakes:

• Ignoring duplicates when finding next bigger element
• Not reversing suffix after swap
• Assuming next permutation is sorted ascending always