Wednesday, October 27, 2010

next_permutation in Java

A few TopCoder SRM problems could be solved by using the next permutation function. Since the next_permutation() function is already available in the C++ library it becomes a sort of a disadvantage for the Java coders. Therefore most of the Java coders have this function in their templates. Here is the implementation in java

public static int[] nextperm(int[] vals) {
int i = vals.length-1;
while (true) {
int ii = i;
i--;
if (vals[i] <>
int j = vals.length;
while (vals[i] >= vals[--j]);
int temp = vals[i]; //Swap
vals[i] = vals[j];
vals[j] = temp;
int begin = ii, end = vals.length-1;
while (end>begin) {
int stemp = vals[end]; //Swap
vals[end] = vals[begin];
vals[begin] = stemp;
end--; begin++;
}
return vals;
} else if (vals[i] == vals[0]) {
int begin = 0, end = vals.length-1;
while (end>begin) {
int stemp = vals[end]; //Swap
vals[end] = vals[begin];
vals[begin] = stemp;
end--; begin++;
}
return vals;
}
}
}

No comments:

Post a Comment