Next Permutation - C Solution

1. Introduction

This blog post discusses a fascinating problem in array manipulation using C programming: finding the next permutation of an array of integers. This challenge is a test of understanding permutations, lexicographical ordering, and efficient in-place array operations.

Problem

The task is to find the next permutation of an array of integers in lexicographical order. If the current arrangement is the highest possible order, the array should be rearranged to its lowest possible order (i.e., sorted in ascending order). The solution must be implemented in-place with constant extra memory.

2. Solution Steps

1. Start from the end of the array and find the first pair of consecutive elements (nums[i], nums[i+1]), where nums[i] < nums[i+1].

2. If such a pair is found, find the smallest element greater than nums[i] from the elements to the right of nums[i].

3. Swap these two elements.

4. Reverse the sub-array to the right of nums[i] to get the next permutation.

5. If no such pair is found, reverse the entire array.

3. Code Program

#include <stdio.h>

// Function to swap elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to reverse a sub-array
void reverse(int *nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start++;
        end--;
    }
}

// Function to find the next permutation
void nextPermutation(int *nums, int numsSize) {
    int i, j;
    for (i = numsSize - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            break;
        }
    }

    if (i >= 0) {
        for (j = numsSize - 1; j > i; j--) {
            if (nums[j] > nums[i]) {
                break;
            }
        }
        swap(&nums[i], &nums[j]);
    }

    reverse(nums, i + 1, numsSize - 1);
}

// Main function to demonstrate nextPermutation function
int main() {
    int nums[] = {1, 2, 3}; // Example input
    int numsSize = sizeof(nums) / sizeof(nums[0]);

    nextPermutation(nums, numsSize); // Call the function

    // Print the next permutation
    printf("Output: ");
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

Output:

1 3 2

Explanation:

The program finds the next permutation of the array [1, 2, 3]. It starts by looking for the first decreasing element from the end, which is 2 in this case. 

Then, it finds the smallest element greater than 2 to the right, which is 3. These elements are swapped, resulting in [1, 3, 2]. Since no reversal is needed after the swap, the final output is [1, 3, 2]. 

This algorithm efficiently computes the next lexicographical permutation in place, demonstrating an understanding of permutation generation in array manipulation.