首页 > 上网技巧 > 电脑小技巧 > Java基于递归解决全排列问题算法示例

Java基于递归解决全排列问题算法示例

时间:2021-06-04 22:53 作者:QQ地带 我要评论

排列问题
 
设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}。集合x中元素的全排列记为Perm(X)。(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳如下:
 
当n=1时,Perm(R)=(r),其中r是集合中唯一的元素;
 
当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)。。。。(rn)Perm(Rn)构成。
 
[java] view plaincopy
public class AllSort {  
public static void perm(int[] list, int k, int m) {  
if( k == m) {  
for (int i = 0; i <=m; i++) {  
System.out.print(list[i]);  
}  
System.out.println();  
}  
else{  
for(int i = k; i <= m; i++) {  
swap(list,k,i);  
perm(list, k+1 , m);  
swap(list,k,i);  
}  
}  
}  
public static void swap(int[] list, int a, int b) {  
int temp;  
temp = list[a];  
list[a] = list[b];  
list[b] = temp;  
}  
public static void main(String args[]) {  
int[] list = new int[5];  
for(int i = 0; i < list.length; i++) {  
list[i] = i+1;  
}  
perm(list,0,list.length-1);  
}  
}  
运行结果:
 
[java] view plaincopy
12345  
12354  
12435  
12453  
12543  
12534  
13245  
13254  
13425  
13452  
13542  
13524  
14325  
14352  
14235  
14253  
14523  
14532  
15342  
15324  
15432  
15423  
15243  
15234  
21345  
21354  
21435  
21453  
21543  
21534  
23145  
23154  
23415  
23451  
23541  
23514  
24315  
24351  
24135  
24153  
24513  
24531  
25341  
25314  
25431  
25413  
25143  
25134  
32145  
32154  
32415  
32451  
32541  
32514  
31245  
31254  
31425  
31452  
31542  
31524  
34125  
34152  
34215  
34251  
34521  
34512  
35142  
35124  
35412  
35421  
35241  
35214  
42315  
42351  
42135  
42153  
42513  
42531  
43215  
43251  
43125  
43152  
43512  
43521  
41325  
41352  
41235  
41253  
41523  
41532  
45312  
45321  
45132  
45123  
45213  
45231  
52341  
52314  
52431  
52413  
52143  
52134  
53241  
53214  
53421  
53412  
53142  
53124  
54321  
54312  
54231  
54213  
54123  
54132  
51342  
51324  
51432  
51423  
51243  
51234  

标签: java
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告