代码实现给a[n]数组进行全排序,找到一个组合的前一个组合,比如a[3]{[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]},给出[2,3,1,],找到他的前序是[2,1,3]
时间: 2023-10-04 16:13:50 浏览: 26
以下是给数组进行全排列,并找到指定组合的前一个组合的Java代码实现:
```java
import java.util.Arrays;
public class Permutation {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] prev = prevPermutation(a, new int[]{2, 3, 1});
System.out.println(Arrays.toString(prev));
}
public static int[] prevPermutation(int[] a, int[] b) {
int n = a.length;
Arrays.sort(a); // 先将数组按升序排列,以便找到第一个组合
int[] prev = null;
do {
if (Arrays.equals(a, b)) { // 找到指定组合
break;
}
prev = Arrays.copyOf(a, n); // 记录当前组合
a = nextPermutation(a); // 继续寻找下一个组合
} while (a != null);
return prev;
}
public static int[] nextPermutation(int[] a) {
int n = a.length;
int i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) {
i--;
}
if (i < 0) {
return null;
}
int j = n - 1;
while (j >= 0 && a[j] <= a[i]) {
j--;
}
swap(a, i, j);
reverse(a, i + 1, n - 1);
return a;
}
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void reverse(int[] a, int i, int j) {
while (i < j) {
swap(a, i++, j--);
}
}
}
```
运行结果为:
```
[2, 1, 3]
```
其中,`prevPermutation` 方法实现了先将数组按升序排列,然后循环调用 `nextPermutation` 方法找到指定组合的前一个组合;`nextPermutation` 方法实现了上述字典序算法;`swap` 方法实现了交换数组中两个元素的功能;`reverse` 方法实现了翻转数组中指定范围内的元素的功能。