java previous permutation

Solutions on MaxInterview for java previous permutation by the best coders in the world

showing results for - "java previous permutation"
Agustín
23 Sep 2018
1public static boolean prev_permutation(int[] arr) {
2	int len = arr.length;
3	int i = len - 1;
4
5    // 1. find largest i where arr[i - 1] > arr[i]
6	while (i > 0) {
7		if (arr[i - 1] > arr[i]) break;
8    	i--;
9  	}
10
11  	if (i <= 0) return false;
12
13  	// 2. find largest j where arr[i - 1] > arr[j] and j >= i
14  	int j = len - 1;
15  	while (j >= i) {
16    	if (arr[i - 1] > arr[j]) break;
17    	j--;
18  	}
19
20	// 3. swap elements between arr[i-1] and arr[j]
21  	swap(i - 1, j, arr);
22
23  	// 4. reverse elements from i to end of array
24  	len--;
25  	while (i < len) {
26    	swap(i, len, arr);
27    	len--;
28    	i++;
29  	}
30  	return true;
31}
32
33public static void swap(int x, int y, int[] arr) {
34  	int temp = arr[x];
35  	arr[x] = arr[y];
36  	arr[y] = temp;
37}