先说一下全排列：
对于R={r1,r2,…,rn}，进行n个元素的全排列，设Ri=R – {ri}。结合X元素的全排列记为Perm(X)，(ri)Perm(X)表示在全排列Perm(X)的每个排列前面加上前缀ri的得到的序列。R的全排列可归纳定义如下：
n=1时，Perm(R)=(r)，其中r是R中的唯一元素；
n>1时，Perm(R)由(r1)Perm(R1), (r2)Perm(R2),…, (rn)Perm(Rn)构成。
显然，部分排列，只要控制递归结束条件即可。
再说组合：
组合与排列相比，忽略了元素的次序，因此我们只需将元素按编号升序排列（或则其他的规则）即可。
代码如下：
public class Main 
{
static int count;
public static void main(String[] args) {
int a[] = {1, 2, 3, 4};
count = 0;
permutation(a, 0, 4);
System.out.println("count=" + count);
count = 0;
combination(a, 0, 3, 0);
System.out.println("count=" + count);
}
static void combination(int a[], int nowp, int m, int left){//zuhe
/**//*
* 求a[]中m个元素的组合
* nowp表示当前已经组合好的元素的个数
* left，只能选择编号为left和它之后的元素 进行交换
*/
if(nowp == m){
count++;
for(int i = 0; i < m; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
else{
for(int i = left; i < a.length; i++){
swap(a, nowp, i);
combination(a, nowp + 1, m, i + 1);
swap(a, nowp, i);
}
}
}
static void permutation(int a[], int nowp, int m){// pailie
/**//*
* 求a[]m个元素的排列
* nowp，当前已经排列好的元素的个数
*/
if(nowp == m){
count++;
for(int i = 0; i < m; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
else{
for(int i = nowp; i < a.length; i++){
swap(a, i, nowp);
permutation(a, nowp + 1, m);
swap(a, i, nowp);
}
}
}
static void swap(int a[], int n, int m){
int t = a[n];
a[n] = a[m];
a[m] = t;
}
}
posted on 2013-07-06 10:54
小鼠标 阅读(1320)
评论(0) 编辑 收藏 引用 所属分类:
Java基础练习