Algorithms
Next even permutation of a number
Given a number N. Find the smallest even number greater than N such that the digits are a permutation of the number N.
A trivial solution to start with would be to generate all the permutations of digits of the given number and then sort all the permutations. The first even permutation in the sorted list that appears after N would be the desired next even permutation. Very easy solution, right? Yeah. But this comes with a high price of generating all permutation in exponential order of time. We could always do better if we closely look at the problem itself. In few seconds we’ll device an algorithm without generating all the permutations. First let’s solve simpler problem, how to find next permutation in sorted sequence of permutations.
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);
}
Next Even Permutation
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.
- 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.
- Let, b = smallest element in y greater than a. This is O(n).
For N = 8234 | 961, with a=4 we have b=6.
- swap (a,b); This is O(1).
After swapping: N = 8236 | 941; X=8236, Y=941.
- 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
- swap max even with the right most digit. This is O(1).
After swapping: N= 8236 | 914; X=8234, Y=914.
- 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;
}