Lexicographic Order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters. This generalization consists primarily in defining a total order on the sequences (often called strings in computer science) of elements of a finite totally ordered set, often called an alphabet.
I’m going to show how to take any permutation and generate the next one in lexicographic order.
For the impatient, we will start with the actual algorithm. Here it is. Suppose that P[1..n] is a permutation of 1 through n. We can construct the next permutation in lexicographic order by following these simple steps:
- Find the largest x such that P[x]<P[x+1].
(If there is no such x, P is the last permutation.) - Find the largest y such that P[x]<P[y].
- Swap P[x] and P[y].
- Reverse P[x+1 .. n].
public class Solution {
public static int[] swap(int arr[], int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2 };
int x = -1;
int y = -1;
boolean flag = false;
//Step 1
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i] > arr[i - 1]) {
x = i - 1;
flag = true;
break;
}
}
if (flag == false) {
System.out.println("no answer");
} else {
//Step 2
for (int i = x; i < arr.length; i++) {
if (arr[x] < arr[i]) {
y = i;
}
}
//step 1
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
int count = 1;
//Step 4
for (int i = x + 1; i < arr.length - ((arr.length - x - 1) / 2); i++) {
int tempS = arr[i];
arr[i] = arr[arr.length - count];
arr[arr.length - count] = tempS;
count++;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
}
}
}
}
Computer Science and Software Engineering 
Leave a comment