Next even permutation of a number - Algorithms and Problem SolvingAlgorithms and Problem Solving

Next even permutation of a number - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a number N. Find the smallest even number greater than N such that the digits are a permutation of the number N.

Let's start with an example, N = 8234961 
We will follow the similar algorithm as above with added checks and swaps to maintain even number.

1. Detect the longest increasing (non-decreasing) sequence Y from right to left and split the input into N=X | Y. This is O(n). Let a be the element where the increasing sequence disrupted. Also keep track that an even does exist in Y.
   

   ---

   N = 8234 | 961,  X=8234, Y=961,  a=4, and evenExist = true

   ---

   Here, we might have a special case if  Y doesn't contain an even digit. In this case extend x to left the point where we have found an even on the left. For example: N = 425731; X=425, yY= 731, a=5, and evenExist=FALSE. Then we extend Y. Now, with extended  Y = 5731, X=42, a=2.
2.  Let, b = smallest element in y greater than a. This is O(n).
   

   ---

   For N = 8234 | 961, with a=4 we have  b=6.

   ---

3.  swap (a,b);  This is O(1). 
   

   ---

   After swapping: N = 8236 | 941;  X=8236,  Y=941.

   ---

4. Find max even in Y. This is O(n).
   

   ---

   N= 8236 | 941;  X=8234,  Y=941, Max even = 4.
   Special case: After swapping it may happen that there is no even in y. So, we need to constantly satisfy that y contains an even after swapping X[a] with the Y[b]. So, keeping this constraint true we will extend y to more left until we find an even. Consider this example: 125831

   ---

5. swap max even with the right most digit. This is O(1).
   

   ---

   After swapping: N= 8236 | 914;  X=8234,  Y=914.

   ---

6.  Now, sort y in decreasing order from right to left leaving rightmost digit unchanged. This is O(nlgn) in worst case.  
   

   ---

   With N= 8236 | 91 | 4 , after sorting  N= 8236 | 19 | 4;

   ---

That's it, now N=xy is the desired solution.

public static void swap(final int[] a, final int i, final int j) {
    if (i == j || i < 0 || j < 0 || i > a.length - 1 || j > a.length - 1) {
        return;
    }
    a[i] ^= a[j];
    a[j] ^= a[i];
    a[i] ^= a[j];
}

public static int[] nextEven(final int[] digits) {
    int y = digits.length - 1;
    boolean evenFound = digits[y] % 2 == 0;
    // find longest increasing subarray from right to left
    for (int i = digits.length - 2; i >= 0; i--) {
        if (digits[i] >= digits[i + 1]) {
            evenFound |= digits[i] % 2 == 0;
            y = i;
        } else {
            break;
        }
    }

    int maxEven = -1;
    // if y doesn’t contain an even then extend y to left until an even found
    while (!evenFound && y - 1 >= 0 && digits[y - 1] % 2 != 0) {
        y--;
    }

    // input is already the largest permutation
    if (y <= 0) {
        return digits[digits.length - 1] % 2 == 0 ? digits : null;
    }

    //try to extend Y such that y contains an even after swapping X[a] with the Y[b]
    while(y -1 >= 0){
     // now X = digits[0..y-1], and Y = digits[y..digits.length-1]
     // a is the rightmost element of x, i.e. a = y-1;
     // find b = min of y greater than a
     final int a = y - 1;
     int b = -1;
     for (int i = y; i < digits.length; i++) {
         b = digits[i] > digits[a] && (b == -1 || (digits[i] < digits[b])) ? i : b;
     }

     // input is already the largest permutation
     if (b == -1) {
         return digits[digits.length - 1] % 2 == 0 ? digits : null;
     }
     // swap a and b
     swap(digits, a, b);

     // update max even in y
     for (int i = y; i < digits.length; i++) {
         maxEven = digits[i] % 2 == 0 && (maxEven == -1 || (maxEven != -1 && digits[i] > digits[maxEven])) ? i
                 : maxEven;
     }

     // input is already the largest permutation or need to extend y
     if (maxEven == -1) {
      y--;
     }
     else{
      break;
     }
    }
     
    if (maxEven == -1) {
        return digits[digits.length - 1] % 2 == 0 ? digits : null;
    }

    // swap max even with rightmost position
    swap(digits, maxEven, digits.length - 1);
    // sort y leaving rightmost position unchanged
    Arrays.sort(digits, y, digits.length - 1);

    return digits;
}

Next Permutation
Observe that if all the digits are in non-decreasing order from right to left then the input itself is the biggest permutation of its digits. So, if we can detect the position where the non-decreasing sequence in disrupted then we can simply work on the part of the digits. We can do it in O(n) using the following (Wiki page also described this simple and efficient algorithm).

1. Find the largest index k such that nums[k] < nums[k + 1]. 
2. If no such index exists, the permutation is sorted in descending order, just reverse it to ascending order and we are done. For example, the next permutation of [3, 2, 1] is [1, 2, 3].
3. Find the largest index l greater than k such that nums[k] < nums[l].
4 Swap the value of nums[k] with that of nums[l].
5. Reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].

 public static void reverse(int A[], int i, int j){
  while(i != j){
   swap(A, i, j);
   i++;
   j--;
  }
 }
 
 public static void nextPermutation(int[] nums) {
        int k = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                k = i;
                break;
            }
        } 
        if (k == -1) {
            reverse(nums, 0, nums.length-1);
            return;
        }
        int l = -1;
        for (int i = nums.length - 1; i > k; i--) {
            if (nums[i] > nums[k]) {
                l = i;
                break;
            } 
        } 
        swap(nums, k, l);
        reverse(nums, k + 1, nums.length-1); 
    }

Read full article from Next even permutation of a number - Algorithms and Problem SolvingAlgorithms and Problem Solving