Why Next Permutation of Array in DSA C?

The Big Idea

What if you could instantly find the very next bigger number arrangement without trying every possibility?

The Scenario

Imagine you have a list of numbers representing a password or a code, and you want to find the very next code that is just a little bigger than the current one. Doing this by hand means trying every possible combination one by one, which can take forever if the list is long.

The Problem

Manually checking every possible order is slow and tiring. You might miss some combinations or make mistakes. It's like trying to find the next page in a huge book by flipping every page instead of knowing exactly where to go.

The Solution

The next permutation method quickly finds the next bigger arrangement of numbers without checking all possibilities. It uses a smart way to find where the order breaks and swaps numbers to get the next code in order.

Before vs After

✗ Before

int arr[] = {1, 2, 3};
// Try all permutations manually to find next bigger one
// Very slow and complex

✓ After

int arr[] = {1, 2, 3};
next_permutation(arr, 3);
// Directly gets next bigger arrangement

What It Enables

This lets you quickly jump to the next bigger arrangement of numbers, making tasks like generating passwords, solving puzzles, or ordering data much faster and easier.

Real Life Example

When you want to generate the next possible password combination or find the next arrangement of seats in a theater, next permutation helps you move forward without repeating or missing any option.

Key Takeaways

Manual checking of all orders is slow and error-prone.

Next permutation finds the next bigger order quickly and smartly.

This method helps in many real-world tasks needing ordered arrangements.

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

   The next permutation is the immediate next arrangement that is greater than the current one in lexicographic 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 arrangement [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly swaps two integers a and b using a temporary variable?

easy

A. a = a + b; b = a - b; a = a - b;

B. a = b; b = a;

C. int temp; a = b; b = temp;

D. int temp = a; a = b; b = temp;

Solution

1. Step 1: Understand swapping with a temporary variable

   Use a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = a; a = b; b = temp; correctly uses a temp variable to swap values safely.

3. Final Answer:

   int temp = a; a = b; b = temp; -> Option D

4. Quick Check:

   Swap with temp variable = int temp = a; a = b; b = temp; [OK]

Hint: Use temp variable to swap safely [OK]

Common Mistakes:

• Assigning a = b; b = a; loses original value
• Using arithmetic swap without considering overflow
• Not declaring or initializing temp variable

3. What is the output of the following C code that finds the next permutation of the array arr = {1, 3, 2}?

void nextPermutation(int* arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
    int left = i + 1, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

int main() {
    int arr[] = {1, 3, 2};
    nextPermutation(arr, 3);
    for (int i = 0; i < 3; i++) printf("%d ", arr[i]);
    return 0;
}

medium

A. 1 2 3

B. 1 3 2

C. 2 1 3

D. 3 1 2

Solution

1. Step 1: Find the pivot index i

   Start from right: arr[1]=3, arr[2]=2, since 3 >= 2, i moves left to 0 where arr[0]=1 < arr[1]=3, so i=0.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[2]=2 > 1, so j=2. Swap arr[0] and arr[2]: arr becomes {2, 3, 1}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=1 to end: reverse {3,1} to {1,3}. Final array: {2,1,3}.

4. Final Answer:

   2 1 3 -> Option C

5. 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 with wrong element j
• Stopping pivot search too early

4. Identify the bug in the following C function that attempts to compute the next permutation of an array arr of size n:

void nextPermutation(int* arr, int n) {
    int i = n - 1;
    while (i > 0 && arr[i] <= arr[i - 1]) i--;
    if (i > 0) {
        int j = n - 1;
        while (arr[j] <= arr[i - 1]) j--;
        int temp = arr[i - 1]; arr[i - 1] = arr[j]; arr[j] = temp;
    }
    int left = i, right = n - 1;
    while (left < right) {
        int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
        left++; right--;
    }
}

medium

A. The swap should be done with arr[i], not arr[i - 1]

B. The initial value of i should be n - 2, not n - 1

C. The reversal loop should start from i - 1, not i

D. The comparison in the first while loop should be arr[i] >= arr[i - 1]

Solution

1. Step 1: Analyze the pivot search loop

   The pivot is found by moving left from n-2, but here i starts at n-1, which skips checking the last pair correctly.

2. Step 2: Correct initial i value

   Setting i = n - 2 ensures the loop compares arr[i] and arr[i+1] properly to find the pivot.

3. Final Answer:

   The initial value of i should be n - 2, not n - 1 -> Option B

4. Quick Check:

   Pivot search starts at n-2 index [OK]

Hint: Start pivot search at n-2 index [OK]

Common Mistakes:

• Starting pivot index at n-1 causes missed comparisons
• Incorrect comparison operators in loops
• Reversing wrong subarray segment

5. Given an array arr = {5, 4, 7, 5, 3, 2}, what will be the next permutation after applying the standard next permutation algorithm?

hard

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

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

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

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

Solution

1. Step 1: Find pivot index i

   Traverse from right: arr[4]=3, arr[5]=2 (3 >= 2), move left; arr[3]=5, arr[4]=3 (5 >= 3), move left; arr[2]=7, arr[3]=5 (7 >= 5), move left; arr[1]=4, arr[2]=7 (4 < 7), so i=1.

2. Step 2: Find j to swap with i

   From right, find j where arr[j] > arr[i]: arr[5]=2 (2 > 4? No), arr[4]=3 (3 > 4? No), arr[3]=5 (5 > 4? Yes), so j=3. Swap arr[1] and arr[3]: arr becomes {5,5,7,4,3,2}.

3. Step 3: Reverse suffix after i

   Reverse elements from i+1=2 to end: reverse {7,4,3,2} to {2,3,4,7}. Final array: {5,5,2,3,4,7}.

4. Final Answer:

   [5, 5, 2, 3, 4, 7] -> Option A

5. Quick Check:

   Next permutation of [5,4,7,5,3,2] = [5,5,2,3,4,7] [OK]

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

Common Mistakes:

• Not finding correct pivot index
• Swapping with wrong element j
• Not reversing suffix correctly