用Java实现给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 12:13:54 浏览: 31
可以使用字典序算法来解决这个问题。具体步骤如下:
1. 从右往左找到第一个比后面数字小的数,记为 a[i]。
2. 在 a[i+1] 到 a[n-1] 中找到比 a[i] 大的数中最小的一个,记为 a[j]。
3. 交换 a[i] 和 a[j]。
4. 将 a[i+1] 到 a[n-1] 排序,使其从小到大排列。
例如,对于数组 [1, 2, 3],其全排列为 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]。
要找到 [2, 3, 1] 的前一个排列,按照上述步骤进行操作:
1. 找到比后面数字小的数,即 2。
2. 在 [3, 1] 中找到比 2 大的数中最小的一个,即 3。
3. 交换 2 和 3,得到 [3, 2, 1]。
4. 将 [2, 1] 排序,得到 [1, 2]。
因此,[2, 3, 1] 的前一个排列为 [2, 1, 3]。
相关问题
用Java对一个数组进行快速排序,给出代码实现
可以使用快速排序算法对一个数组进行排序,Java代码实现如下:
```
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
```
这段代码实现了快速排序算法,其中 partition 方法用于将数组分为两部分,并返回中间值的下标,quickSort 方法则递归调用 partition 方法,对左右两部分进行排序。
java 实现n个数组排列组合
要实现n个数组的排列组合,可以使用递归算法。
首先,我们定义一个函数,输入参数为n个数组和一个空的结果列表。函数的作用是将n个数组进行排列组合,并将所有组合的结果保存在结果列表中。
然后,在函数中,我们使用两个循环嵌套来对数组进行排列组合。外层循环用于遍历数组的第一个元素,内层循环用于遍历其余n-1个数组的所有可能组合。
在内层循环中,我们将当前数组的第一个元素与剩余n-1个数组的所有可能组合拼接成新的组合,并递归调用函数。递归调用的参数为剩余的n-1个数组和拼接后的结果列表。
当递归调用的参数数组为空时,表示已经排列组合完成,将结果列表保存到最终的结果集中。
最后,返回最终的结果集。
下面是一个具体实现的示例代码:
```java
import java.util.ArrayList;
import java.util.List;
public class PermutationCombination {
public static void main(String[] args) {
int[][] arrays = {{1, 2, 3}, {4, 5}, {6, 7, 8}};
List<List<Integer>> result = new ArrayList<>();
permutationCombination(arrays, new ArrayList<>(), result);
System.out.println(result);
}
private static void permutationCombination(int[][] arrays, List<Integer> current, List<List<Integer>> result) {
if (arrays.length == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < arrays[0].length; i++) {
current.add(arrays[0][i]);
int[][] remaining = new int[arrays.length - 1][];
for (int j = 1; j < arrays.length; j++) {
remaining[j - 1] = arrays[j];
}
permutationCombination(remaining, current, result);
current.remove(current.size() - 1);
}
}
}
```
运行上述代码,输出结果为:
[[1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 5, 6], [1, 5, 7], [1, 5, 8], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 5, 6], [2, 5, 7], [2, 5, 8], [3, 4, 6], [3, 4, 7], [3, 4, 8], [3, 5, 6], [3, 5, 7], [3, 5, 8]]
以上代码实现了将3个数组进行排列组合的功能,你可以根据需要修改输入数组的个数来实现任意个数组的排列组合。