java输出1-n全排列_生成1~n的全排列
时间: 2024-02-25 15:57:11 浏览: 17
生成1~n的全排列可以使用回溯算法,具体步骤如下:
1. 定义一个数组,存放1~n的数字;
2. 定义一个visited数组,记录数字是否被使用过;
3. 定义一个StringBuilder变量,用于存储当前排列;
4. 定义一个count变量,记录已经生成的排列个数;
5. 使用回溯算法,依次枚举数组中的每个数字,如果该数字没有被使用过,则将其加入当前排列中,标记为已使用,然后递归调用生成下一个数字的排列;
6. 如果已经生成了n个数字,则输出当前排列,count加1;
7. 回溯到上一个状态,将该数字从当前排列中删除,标记为未使用。
具体实现代码如下:
```java
public class Permutation {
public static void main(String[] args) {
int n = 3;
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
boolean[] visited = new boolean[n];
StringBuilder sb = new StringBuilder();
int count = 0;
generatePermutation(nums, visited, sb, count);
}
private static void generatePermutation(int[] nums, boolean[] visited, StringBuilder sb, int count) {
if (count == nums.length) { // 已经生成了n个数字
System.out.println(sb.toString());
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
sb.append(nums[i]);
generatePermutation(nums, visited, sb, count + 1);
sb.deleteCharAt(sb.length() - 1);
visited[i] = false;
}
}
}
}
```
当n为3时,输出的全排列如下:
```
123
132
213
231
312
321
```