聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

排列组合

2013-07-07 08:40 浏览: 1115416 次 我要评论(0 条) 字号:

先说一下全排列:

对于R={r1,r2,…,rn},进行n个元素的全排列,设Ri=R – {ri}。结合X元素的全排列记为Perm(X)(ri)Perm(X)表示在全排列Perm(X)的每个排列前面加上前缀ri的得到的序列。R的全排列可归纳定义如下:

n=1时,Perm(R)=(r),其中rR中的唯一元素;

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[] = {1234};
        count 
= 0;
        permutation(a, 
04);
        System.out.println(
"count=" + count);
        
        count 
= 0;
        combination(a, 
030);
        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;
    }


}




小鼠标 2013-07-06 10:54 发表评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复