Next Permutation of Array in DSA C++ - Deep Dive

Overview - Next Permutation of Array

What is it?

Next Permutation of Array is a way to rearrange numbers into the next bigger order using the same numbers. It finds the closest larger arrangement than the current one. If no bigger arrangement exists, it resets to the smallest order. This helps in problems where we want to explore all possible orders step-by-step.

Why it matters

Without next permutation, finding the next bigger order would be slow and complicated, especially for large arrays. It helps in generating sequences in order, which is useful in puzzles, optimization, and algorithms that need to try all possibilities efficiently. Without it, many problems would require expensive sorting or guessing.

Where it fits

Before learning this, you should understand arrays and basic sorting. After this, you can explore permutations generation, backtracking, and combinatorial algorithms that use permutations to solve complex problems.

Mental Model

Core Idea

Next permutation finds the next bigger number by changing the smallest possible part of the array to get the next order.

Think of it like...

Imagine you have a lock with digits. Next permutation is like turning the lock to the next combination that is just a little bigger than the current one, without skipping any combinations.

Array: [1, 2, 3]
Find pivot: from right, find first number smaller than next
Swap pivot with just bigger number on right
Reverse suffix after pivot

Example:
1 2 3
  ↑ pivot at 2
Swap 2 with 3
1 3 2
Reverse suffix after pivot (only last element)
Result: 1 3 2

Build-Up - 6 Steps

1

Foundation

Understanding Permutations and Order

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

A permutation is a way to arrange items in order. For example, for [1, 2, 3], permutations include [1, 2, 3], [1, 3, 2], [2, 1, 3], etc. These can be sorted in ascending order to list all possible arrangements.

Result

You understand that permutations can be listed in a sorted order from smallest to largest.

Knowing that permutations have a natural order helps us find the 'next' one without listing all.

2

Foundation

Identifying the Pivot Point in Array

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

Starting from the right end of the array, move left until you find a number smaller than the number immediately after it. This is the pivot point where we can make the next bigger permutation.

Result

You can find the pivot index or know if the array is the highest permutation already.

The pivot marks where change is needed to get a bigger permutation.

3

Intermediate

Finding the Right Swap Candidate

🤔Before reading on: do you think we swap the pivot with the smallest or largest number on the right? Commit to your answer.

Concept: Swap the pivot with the smallest number larger than it on the right side.

After finding the pivot, scan from the right to find the smallest number greater than the pivot. Swap these two to increase the permutation just enough.

Result

The array now has a bigger number at the pivot position, moving towards the next permutation.

Swapping with the smallest bigger number ensures the next permutation is the closest larger one.

4

Intermediate

Reversing the Suffix After Pivot

🤔Before reading on: do you think we sort or reverse the suffix after swapping? Commit to your answer.

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

After swapping, the suffix (right part) is in descending order. Reversing it makes it ascending, which is the smallest order and ensures the next permutation is minimal bigger.

Result

The array is now the next permutation in lexicographic order.

Reversing the suffix resets it to the smallest order, completing the next permutation.

5

Advanced

Handling the Last Permutation Case

🤔Before reading on: do you think the next permutation exists for the highest order array? Commit to your answer.

Concept: If no pivot is found, the array is the highest permutation and must reset to the lowest.

If the array is sorted descending (like [3, 2, 1]), no next bigger permutation exists. We reverse the whole array to get the smallest permutation (ascending order).

Result

The array resets to the smallest permutation, allowing cycling through all permutations.

Knowing when to reset prevents errors and allows continuous permutation generation.

6

Expert

Optimizing In-Place Next Permutation Algorithm

🤔Before reading on: do you think extra memory is needed for next permutation? Commit to your answer.

Concept: The algorithm works in-place with O(1) extra space and O(n) time by careful scanning and reversing.

By scanning from right to left and reversing the suffix in-place, we avoid extra memory. This is efficient for large arrays and used in standard libraries.

Result

Next permutation is computed quickly and memory-efficiently.

Understanding in-place operations helps write efficient code for real-world constraints.

Under the Hood

The algorithm scans from the right to find the pivot where the order breaks ascending. It then finds the smallest number larger than the pivot to swap, ensuring the next bigger number. Finally, it reverses the suffix to get the smallest order after the pivot. 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 generate permutations in lexicographic order efficiently without generating all permutations. Alternatives like generating all permutations and sorting are expensive. The in-place approach saves memory and time, making it practical for large inputs.

Array: [a1, a2, ..., apivot, ..., an]

Step 1: Find pivot (apivot < apivot+1)
Step 2: Find swap candidate (smallest ai > apivot for i > pivot)
Step 3: Swap apivot and ai
Step 4: Reverse suffix (apivot+1 to an)

┌─────────────┬───────────────┐
│ Left part   │ Right suffix  │
│ (unchanged) │ (reversed)    │
└─────────────┴───────────────┘

Myth Busters - 4 Common Misconceptions

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

Common Belief: Next permutation always changes the first element to a bigger number.

Reality: Next permutation changes the smallest possible part from the right; the first element may stay the same.

Why it matters: Assuming the first element always changes can lead to wrong code that breaks the algorithm's correctness.

Quick: Is sorting the suffix after swapping necessary? Commit yes or no.

Common Belief: After swapping, sorting the suffix is needed to get the next permutation.

Reality: Reversing the suffix is enough because it is in descending order before reversal, so reversing sorts it ascending.

Why it matters: Sorting is more expensive; reversing is faster and simpler, so misunderstanding this wastes time and resources.

Quick: Can next permutation generate permutations out of order? Commit yes or no.

Common Belief: Next permutation can skip some permutations or generate them out of order.

Reality: Next permutation generates all permutations in exact lexicographic order without skipping.

Why it matters: Believing it skips permutations can cause bugs in algorithms relying on complete ordered generation.

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 intermediate results.

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

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

Expert Zone

1

The pivot search is a linear scan from right, but early stopping is possible once the pivot is found, improving average speed.

2

Reversing the suffix is optimal because the suffix is guaranteed to be in descending order before reversal, avoiding sorting overhead.

3

In some languages, next permutation is implemented as a standard library function, but understanding the algorithm helps customize or debug it.

When NOT to use

Next permutation is not suitable when permutations need to be generated in random order or when skipping permutations is required. Alternatives include Heap's algorithm for generating all permutations without order or using backtracking for selective permutations.

Production Patterns

Used in combinatorial optimization to explore neighboring solutions, in puzzle solvers to generate next states, and in testing frameworks to generate test cases systematically. Also used in lexicographic ranking and unranking of permutations.

Connections

Lexicographic Order

Next permutation builds on the concept of lexicographic order to generate permutations in sorted sequence.

Understanding lexicographic order clarifies why the algorithm reverses the suffix and swaps the pivot.

Backtracking Algorithms

Next permutation can be used as a building block or alternative to backtracking for generating permutations.

Knowing next permutation helps optimize permutation generation compared to recursive backtracking.

Music Composition (Theory)

Both next permutation and musical scales explore ordered sequences with constraints and transitions.

Recognizing patterns in ordered sequences across fields helps appreciate structured progression and minimal changes.

Common Pitfalls

#1 Swapping the pivot with any larger number instead of the smallest larger number.

Wrong approach:

int i = pivot;
int j = n - 1;
while (j > i && arr[j] <= arr[i]) j--;
std::swap(arr[i], arr[n-1]); // wrong: swaps with last element always

Correct approach:

int i = pivot;
int j = n - 1;
while (j > i && arr[j] <= arr[i]) j--;
std::swap(arr[i], arr[j]); // correct: swaps with smallest bigger number

Root cause:

Misunderstanding that any bigger number works instead of the closest bigger number.

#2 Sorting the suffix after swapping instead of reversing it.

Wrong approach:

std::sort(arr.begin() + pivot + 1, arr.end()); // correct but inefficient

Correct approach:

std::reverse(arr.begin() + pivot + 1, arr.end()); // efficient and correct

Root cause:

Not realizing the suffix is in descending order before reversal.

#3 Not handling the case when the array is the highest permutation.

Wrong approach:

If no pivot found, do nothing and return the same array.

Correct approach:

If no pivot found, reverse the whole array to get the lowest permutation.

Root cause:

Missing the reset step causes the algorithm to fail cycling through permutations.

Key Takeaways

Next permutation finds the next bigger arrangement by changing the smallest possible part from the right.

It works by finding a pivot, swapping with the smallest bigger number on the right, and reversing the suffix.

If no bigger permutation exists, it resets to the smallest order by reversing the whole array.

The algorithm runs in-place with O(n) time and O(1) extra space, making it efficient for large arrays.

Understanding next permutation helps in generating permutations in order and solving many combinatorial problems.

Practice

1. What does the next_permutation function do to an array of integers?

easy

A. It rearranges the array to the next lexicographically greater permutation.

B. It sorts the array in ascending order.

C. It reverses the array elements.

D. It finds the maximum element in the array.

Solution

1. Step 1: Understand the purpose of next_permutation

   The function changes the array to the next bigger arrangement in dictionary order.

2. Step 2: Compare with other options

   Sorting or reversing are different operations; next_permutation specifically finds the next lexicographic order.

3. Final Answer:

   It rearranges the array to the next lexicographically greater permutation. -> Option A

4. Quick Check:

   Next permutation = next lexicographic order [OK]

Hint: Think of next_permutation as next dictionary word order [OK]

Common Mistakes:

• Confusing next_permutation with sorting
• Thinking it reverses the array
• Assuming it finds max element

2. Which of the following is the correct syntax to use std::next_permutation on a vector v in C++?

easy

A. std::next_permutation(v.begin(), v.end());

B. std::next_permutation(v);

C. next_permutation(v.begin(), v.end());

D. std::next_permutation(v.start(), v.finish());

Solution

1. Step 1: Recall the correct function signature

   std::next_permutation requires two iterators: begin and end of the container.

2. Step 2: Check each option

   std::next_permutation(v.begin(), v.end()); uses correct syntax with std:: and iterators. std::next_permutation(v); misses iterators. next_permutation(v.begin(), v.end()); misses std::. std::next_permutation(v.start(), v.finish()); uses invalid iterator names.

3. Final Answer:

   std::next_permutation(v.begin(), v.end()); -> Option A

4. Quick Check:

   Use std::next_permutation with begin() and end() [OK]

Hint: Always pass begin() and end() iterators to next_permutation [OK]

Common Mistakes:

• Omitting std:: namespace
• Passing container instead of iterators
• Using wrong iterator names like start() or finish()

3. What will be the output array after applying std::next_permutation once on arr = {1, 3, 2}?

medium

A. [2, 3, 1]

B. [1, 3, 2]

C. [1, 2, 3]

D. [2, 1, 3]

Solution

1. Step 1: Trace the next_permutation algorithm

   Array [1, 3, 2]. Find rightmost pivot i where arr[i] < arr[i+1]: i=0 (1 < 3).

2. Step 2: Find rightmost j > i with arr[j] > arr[i]

   j=2 (2 > 1). Swap i=0 and j=2: [2, 3, 1]. Reverse suffix from 1: [3, 1] -> [1, 3]. Result: [2, 1, 3].

3. Final Answer:

   [2, 1, 3] -> Option D

4. Quick Check:

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

Hint: Swap and reverse suffix to find next permutation [OK]

Common Mistakes:

• Confusing next with previous permutation
• Not reversing suffix after swap
• Assuming array stays same if not sorted

4. Consider the following code snippet:

std::vector<int> v = {3, 2, 1};
std::next_permutation(v.begin(), v.end());
for(int x : v) std::cout << x << ' ';

What is the output and why?

medium

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Recognize input is highest permutation

   The array [3, 2, 1] is sorted descending, so it's the last permutation.

2. Step 2: next_permutation resets to lowest permutation

   Since no next bigger permutation exists, it resets to ascending order [1, 2, 3].

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Last permutation resets to first [OK]

Hint: Last permutation resets to ascending order [OK]

Common Mistakes:

• Expecting no change on last permutation
• Thinking next_permutation always swaps elements
• Ignoring reset behavior

5. Given the array arr = {1, 5, 4, 3, 2}, what is the next permutation after applying std::next_permutation?

hard

A. [1, 5, 2, 3, 4]

B. [1, 5, 4, 2, 3]

C. [2, 1, 3, 4, 5]

D. [1, 5, 4, 3, 2]

Solution

1. Step 1: Find the pivot from right where arr[i] < arr[i+1]

   arr=[1,5,4,3,2]. Check from right: i=3 (3<2? No), i=2 (4<3? No), i=1 (5<4? No), i=0 (1<5 Yes). Pivot=0.

2. Step 2: Find rightmost element > pivot (1) to swap

   Rightmost j>0 with arr[j]>1: j=4 (2>1). Swap 0 and 4: [2,5,4,3,1].

3. Step 3: Swap and reverse suffix

   Reverse suffix after 0: [5,4,3,1] -> [1,3,4,5]. Final: [2,1,3,4,5].

4. Final Answer:

   [2, 1, 3, 4, 5] -> Option C

5. Quick Check:

   Swap pivot and rightmost successor, then reverse suffix [OK]

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

Common Mistakes:

• Swapping wrong elements
• Not reversing suffix after swap
• Confusing pivot index