Sunday, December 21, 2014

Next Permutation

This is much easier than the Permutation Sequence. Even though both of them are math problems. I follow the algorithm in this post. And I am stealing the graph from the post (thank you!).




public class NextPermutation {
    public void nextPermutation(int[] num) {
        if (num == null)
            throw new NullPointerException("Null array!");
        if (num.length == 0)
            return;
        
        int index = num.length - 1;
        while (index > 0 && num[index - 1] >= num[index]) {
            index--;
        }
        //if the whole array is in descending order, reverse the array and return
        if (index == 0) {
            reverse(num, 0, num.length - 1);
            return;
        }
        int pivot = --index;
        index = num.length - 1;
        while (num[index] <= num[pivot]) 
            index--;
        swap(num, pivot, index);
        reverse(num, pivot + 1, num.length - 1);
    }
    private void swap(int[] num, int i, int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
    private void reverse(int[] num, int i, int j) {
        while (i < j) {
            swap(num, i, j);
            i++;
            j--;
        }
    }
}

No comments:

Post a Comment