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.