生成1-n的排列
具体题目为,输入整数n,按字典序大小从小到大顺序输出前n个数的所有排列。
例如输入n=3,则要求得出集合{1,2,3}所有的字典序排列。如{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}
主要思路是利用解答树
image.png
1、在第一个循环中确定第一个数
2、在第二个循环中确定第二个数
.
.
n、在第n个循环中确定第n个数
在n+1个循环中输出排列
具体我是用java进行了实现
public class Meiju {
public void print_permutation(int n, int A[], int cur) {
if (cur == n) { //当第n+1次调用此函数时,输出其排列
System.out.print('[');
for (int i = 0; i < n; i++) {
System.out.print(A[i] + " ");
}
System.out.print(']' + " ");
}
else
for (int i = 1; i <= n; i++) {//尝试在A[cur]填入1~n
boolean ok = true;//重置ok初始值
for (int j = 0; j < cur; j++)
if (A[j] == i) ok = false;//如果i在A[0]-A[cur-1]中出现过,则不填入
if (ok) {//如果 i 没出现过则填入,出现过就继续循环,然后尝试填入i+1
A[cur] = i;
print_permutation(n, A, cur + 1);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int A[] = new int[n];
Meiju test = new Meiju();
test.print_permutation(n, A, 0);
}
}
网友评论