Next Permutation of Array in DSA C - Build from Scratch

Next Permutation of Array

📖 Scenario: Imagine you have a list of numbers representing a code combination. You want to find the next code combination that is just a little bigger than the current one, following a special order.

🎯 Goal: You will write a program in C that finds the next permutation of an array of integers. This means rearranging the numbers to the next bigger order. If no bigger order exists, you will rearrange to the smallest order.

📋 What You'll Learn

Create an integer array called nums with the exact values: 1, 2, 3

Create an integer variable called n that stores the size of nums

Write code to find the next permutation of nums using the standard algorithm

Print the elements of nums separated by spaces after finding the next permutation

💡 Why This Matters

🌍 Real World

Next permutation algorithms are used in generating combinations, solving puzzles, and optimizing sequences in games or scheduling.

💼 Career

Understanding permutation algorithms helps in coding interviews and tasks involving sequence generation or optimization.

1

Create the initial array

Create an integer array called nums with the exact values 1, 2, 3 and an integer variable called n that stores the size of nums.

DSA C

# Create the array nums and the variable n
// Your code here

Hint

Use int nums[] = {1, 2, 3}; to create the array and int n = 3; for its size.

2

Find the pivot index

Add code to find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, set i to -1.

DSA C

#include 

int main() {
    int nums[] = {1, 2, 3};
    int n = 3;

    int i = n - 2;
    // Find the largest index i such that nums[i] < nums[i + 1]
    // Your code here

    return 0;
}

Hint

Start from n - 2 and move left while nums[i] >= nums[i + 1].

3

Find the successor and swap

If i is not -1, find the largest index j greater than i such that nums[j] > nums[i]. Swap nums[i] and nums[j]. Then reverse the subarray from i + 1 to the end.

DSA C

#include 

int main() {
    int nums[] = {1, 2, 3};
    int n = 3;

    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    // If i is not -1, find j and swap nums[i] and nums[j]
    // Then reverse from i+1 to end
    // Your code here

    return 0;
}

Hint

Use a helper function to swap and another to reverse the subarray.

4

Print the next permutation

Print the elements of the array nums separated by spaces after finding the next permutation.

DSA C

#include 

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int arr[], int start, int end) {
    while (start = 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i != -1) {
        int j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(&nums[i], &nums[j]);
    }

    reverse(nums, i + 1, n - 1);

    // Print the array nums separated by spaces
    // Your code here

    return 0;
}

Hint

Use a for loop to print each element with a space, then print a newline.

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