Finding the Next Lexicographical Permutation in Java

Generating permutations of a sequence in lexicographical order is a common algorithmic task. In this blog post, we'll explore how to find the next lexicographically greater permutation of an array using Java.

Understanding Lexicographical Order

Lexicographical order is similar to how words are arranged in a dictionary. For a sequence of numbers, it means arranging them in an order such that each subsequent permutation is "greater" than the previous one. For example, the permutations of {1, 2, 3} in lexicographical order are:

1. [1, 2, 3]

2. [1, 3, 2]

3. [2, 1, 3]

4. [2, 3, 1]

5. [3, 1, 2]

6. [3, 2, 1]

The Algorithm

Our Java code finds the next permutation using the following steps:

1. Find the Breakpoint:

   • Iterate from right to left, finding the first element nums[i] that is smaller than nums[i + 1]. This i is the "breakpoint."

   • If no breakpoint is found, the array is in descending order, and we reverse it to get the smallest permutation.

2. Find the Swap Element:

   • Iterate from right to left again, finding the smallest element nums[j] that is greater than nums[i].

3. Swap:

   • Swap nums[i] and nums[j].

4. Reverse the Suffix:

   • Reverse the subarray starting from nums[i + 1] to the end of the array.

Java Code Implementation

Java

package Arrays;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class NextPermutation {

    public static List<Integer> nextPermutation(int nums[]) {
        List<Integer> l = Arrays.stream(nums).boxed().collect(Collectors.toList());
        int n = l.size();
        int index = -1;

        for (int i = n - 2; i >= 0; i--) {
            if (l.get(i) < l.get(i + 1)) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            Collections.reverse(l);
            return l;
        }

        for (int i = n - 1; i > index; i--) {
            if (l.get(i) > l.get(index)) {
                int temp = l.get(i);
                l.set(i, l.get(index));
                l.set(index, temp);
                break;
            }
        }

        List<Integer> subList = l.subList(index + 1, n);
        Collections.reverse(subList);
        return l;
    }

    public static void main(String[] args) {
        int num[] = {1, 2, 4, 3};
        System.out.println("Next Permutation Lexicographically: " + nextPermutation(num));
    }
}

Explanation:

1. nextPermutation(int nums[]):

   • Converts the input array nums to a List<Integer> for easier manipulation.

   • Finds the breakpoint index.

   • Handles the case where there's no next permutation by reversing the list.

   • Finds the swap element and swaps it with the element at index.

   • Reverses the suffix of the list.

   • Returns the modified list.

2. main(String[] args):

   • Provides an example usage of the nextPermutation method.

Time and Space Complexity

• Time Complexity: O(n), as we iterate through the array a maximum of three times.

• Space Complexity: O(n), due to the conversion to a List. If you modify the original array in place, the space complexity can be reduced to O(1).

Example Usage

For the input array [1, 2, 4, 3], the code will output:

Next Permutation Lexicographically: [1, 3, 2, 4]

Conclusion

This algorithm efficiently finds the next lexicographically greater permutation of an array. It's a useful technique for generating permutations in a specific order and has applications in various combinatorial and optimization problems. By understanding this algorithm, you can effectively solve permutation-related challenges.