Next Permutation

In this problem we have to rearrange the list of numbers into lexicographically next greater permutation of list of numbers.

Problem Explanation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The subsequent permutation of an array of integers refers to the lexicographically next greater permutation of that array. To elaborate, if all the possible permutations of the array are arranged in a container based on their lexicographical order, then the next permutation of the array is the one that immediately follows it in the ordered container. In case such an arrangement is not achievable, the array must be reorganized to the lowest possible order, which is equivalent to sorting it in ascending order.

For example,

• The next permutation of arr = [1,2,3] is [1,3,2].
• The next permutation of arr = [2,3,1] is [3,1,2].
• The next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Hence, the problem statement is ‘Given an array of integers nums, find the next permutation of nums’.

Approach:

1. Find the break-point, i : The first index i from the back of the given array where arr[i] becomes smaller than arr[i+1]. To find the break-point, using a loop we will traverse the array backward and store the index where arr[i] is less than arr[i+1].
2. If any such break-point does not exist it implies that the given permutation is the last one in the sorted order of all possible permutations. Hence, the next permutation must be the first i.e. the permutation in increasing order. So, in this case the answer will be the reverse of the given array.
3. If break-point exists:

1. Find the smallest number i.e. > arr[i] and in the right half of index i(i.e. from index i+1 to n-1) and swap it with arr[i].
2. Reverse the entire right half(i.e. from index i+1 to n-1) of index i. And finally, return the array.

Example

Let the input array be { 1, 3, 2 }

Step 1

Find an increasing sequence.

We take i1 = 1 and traverse backward

Step 2

Since 3 is not less than 2, we decrease i1 by 1

Step 3

Since 1 is less than 2, we have achieved our start of increasing sequence. Now, i1 = 0.

Step 4

i2 will be another index to find just greater than i1 indexed elements in the array. Point i2 to the last element.

Step 5

i2 indexed element is greater than i1 indexed element.

Hence, i2 = 2

Step 6

Swapping values present in i1 and i2

Step 7

Reversing from i1+1 index to last array

Thus, this is the final answer!

Complexity

• Time Complexity: O(3N)
• Space Complexity: O(1)

Where N is the size of the array.

Java Code

import java.util.*;

public class NextPermutation {

    public static List<Integer> nextGreaterPermutation(List<Integer> arr) {

        int n = arr.size(); // size of the array.

        // Step 1: Find the break point:
        int breakPoint = -1; // break point

        for (int i = n - 2; i >= 0; i--) {
            if (arr.get(i) < arr.get(i + 1)) {
                // index i is the break point
                breakPoint = i;
                break;
            }
        }

        //If break point does not exist:
        if (breakPoint == -1) {
            // reverse the whole array:
            Collections.reverse(arr);
            return arr;
        }

        // Step 2: Find the next greater element
        // and swap it with arr[breakPoint]:
        for (int i = n - 1; i > breakPoint; i--) {
            if (arr.get(i) > arr.get(breakPoint)) {
                int tmp = arr.get(i);
                arr.set(i, arr.get(breakPoint));
                arr.set(breakPoint, tmp);
                break;
            }
        }

        // Step 3: reverse the right half:
        List<Integer> sublist = arr.subList(breakPoint + 1, n);
        Collections.reverse(sublist);
        return arr;

    }

    public static void main(String args[]) {

        List<Integer> arr = Arrays.asList(new Integer[] { 1, 3, 2 });
        List<Integer> ans = nextGreaterPermutation(arr);
        System.out.print("The next permutation is: [ ");
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i) + " ");
        }

        System.out.println("]");

    }

}

Output

The next permutation is: [ 2 1 3 ]