先說一下全排列：
對(duì)于R={r1,r2,…,rn}，進(jìn)行n個(gè)元素的全排列，設(shè)Ri=R – {ri}。結(jié)合X元素的全排列記為Perm(X)，(ri)Perm(X)表示在全排列Perm(X)的每個(gè)排列前面加上前綴ri的得到的序列。R的全排列可歸納定義如下：
n=1時(shí)，Perm(R)=(r)，其中r是R中的唯一元素；
n>1時(shí)，Perm(R)由(r1)Perm(R1), (r2)Perm(R2),…, (rn)Perm(Rn)構(gòu)成。
顯然，部分排列，只要控制遞歸結(jié)束條件即可。
再說組合：
組合與排列相比，忽略了元素的次序，因此我們只需將元素按編號(hào)升序排列（或則其他的規(guī)則）即可。
代碼如下：
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個(gè)元素的組合
* nowp表示當(dāng)前已經(jīng)組合好的元素的個(gè)數(shù)
* left，只能選擇編號(hào)為left和它之后的元素 進(jìn)行交換
*/
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個(gè)元素的排列
* nowp，當(dāng)前已經(jīng)排列好的元素的個(gè)數(shù)
*/
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
小鼠標(biāo) 閱讀(1330)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Java基礎(chǔ)練習(xí)