Next Permutation in C#

Programming C#
1

The “Next Permutation” problem is about rearranging the elements of an array or list into the lexicographically next greater permutation. If such an arrangement is not possible (i.e., the array is in descending order), it should be rearranged to the lowest possible order (i.e., sorted in ascending order).

Explanation

The algorithm to find the next permutation can be broken down into the following steps:

  1. Identify the Pivot: Traverse the array from right to left and find the first pair where the earlier element is less than the later element. This element is called the “pivot.” If no such pair exists, it means the array is sorted in descending order, and we should reverse it to get the smallest permutation.

  2. Find the Successor: From the right end of the array, find the smallest element that is larger than the pivot. This element will be swapped with the pivot.

  3. Swap and Reverse: Swap the pivot with the successor, and then reverse the portion of the array to the right of the pivot to get the next permutation.

Code Implementation

Here’s how to implement the next permutation algorithm in C#:

using System;

class Program
{
    static void NextPermutation(int[] nums)
    {
        int n = nums.Length;
        int pivot = -1;

        // Step 1: Find the pivot
        for (int i = n - 2; i >= 0; i--)
        {
            if (nums[i] < nums[i + 1])
            {
                pivot = i;
                break;
            }
        }

        if (pivot == -1)
        {
            // If no pivot found, reverse the entire array
            Array.Reverse(nums);
            return;
        }

        // Step 2: Find the successor to pivot
        for (int i = n - 1; i > pivot; i--)
        {
            if (nums[i] > nums[pivot])
            {
                // Step 3: Swap
                Swap(nums, pivot, i);
                break;
            }
        }

        // Step 4: Reverse the sequence after the pivot
        Array.Reverse(nums, pivot + 1, n - pivot - 1);
    }

    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    static void Main(string[] args)
    {
        int[] nums = { 1, 2, 3 };
        NextPermutation(nums);
        Console.WriteLine("Next permutation: " + string.Join(", ", nums)); // Output: 1, 3, 2
    }
}

How the Code Works

  1. Find the Pivot:

    • Start from the second last element and move leftwards. When you find an element that is smaller than its next element, that’s your pivot.

  2. Check for the End Case:

    • If no pivot is found (meaning the array is in descending order), reverse the entire array.

  3. Find the Successor:

    • Look for the smallest number larger than the pivot from the right end of the array.

  4. Swap Elements:

    • Swap the pivot with the found successor.

  5. Reverse the Suffix:

    • Reverse the part of the array to the right of the pivot to get the next permutation in lexicographic order.

Complexity

  • Time Complexity: O(n), where n is the number of elements in the array. Each of the steps (finding pivot, finding successor, swapping, and reversing) takes linear time.
  • Space Complexity: O(1), as we are modifying the array in place and using a constant amount of extra space.

This approach efficiently finds the next permutation, ensuring that all possible arrangements are considered in lexicographical order.