Next Permutation of Array in DSA C++ - Build from Scratch

Next Permutation of Array

📖 Scenario: You are working on a program that helps generate the next arrangement of numbers in a sequence, like finding the next page in a book of number patterns.

🎯 Goal: Build a program that takes a list of numbers and changes it to the next bigger arrangement of those numbers. If no bigger arrangement exists, it should rearrange to the smallest order.

📋 What You'll Learn

Create a vector called nums with the exact values {1, 2, 3}

Create an integer variable called i to find the first decreasing element from the right

Implement the next permutation logic using i and j to swap and reverse parts of nums

Print the elements of nums separated by spaces

💡 Why This Matters

🌍 Real World

Next permutation is useful in generating all possible arrangements in games, puzzles, and combinatorial problems.

💼 Career

Understanding permutations helps in algorithm design, coding interviews, and solving optimization problems.

1

Create the initial array

Create a vector of integers called nums with the exact values {1, 2, 3}.

DSA C++

# Create the vector nums with values {1, 2, 3}
# Your code here

Hint

Use std::vector<int> and initialize it with {1, 2, 3}.

2

Find the first decreasing element from the right

Add an integer variable called i and set it to nums.size() - 2. Then use a while loop to decrease i while i >= 0 and nums[i] >= nums[i + 1].

DSA C++

#include 
#include 

int main() {
    std::vector nums = {1, 2, 3};
    int i = nums.size() - 2;
    // Find the first decreasing element from the right
    // Your code here
    return 0;
}

Hint

Start from the second last index and move left while the current number is not less than the next.

3

Find the element to swap and reverse the suffix

If i >= 0, create an integer j set to nums.size() - 1. Use a while loop to decrease j while nums[j] <= nums[i]. Then swap nums[i] and nums[j]. After that, reverse the elements from i + 1 to the end of nums using a while loop.

DSA C++

#include 
#include 

int main() {
    std::vector nums = {1, 2, 3};
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    // If i >= 0, find j and swap nums[i] and nums[j]
    // Then reverse from i+1 to end
    // Your code here
    return 0;
}

Hint

Find the rightmost element bigger than nums[i], swap, then reverse the tail part.

4

Print the next permutation

Use a for loop with an integer k from 0 to nums.size() to print each element of nums separated by spaces.

DSA C++

#include 
#include 

int main() {
    std::vector nums = {1, 2, 3};
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = nums.size() - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        std::swap(nums[i], nums[j]);
    }
    int left = i + 1;
    int right = nums.size() - 1;
    while (left < right) {
        std::swap(nums[left], nums[right]);
        left++;
        right--;
    }
    for (int k = 0; k < nums.size(); k++) {
        // Print nums[k] followed by a space
        // Your code here
    }
    return 0;
}

Hint

Use std::cout inside a loop to print each number followed by a space.

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