Java实现排列组合

基本概念

阶乘

在介绍排列组合前首先要介绍阶乘，因为很多排列组合的运算都是要用上阶乘。阶乘的定义如下：一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。
即n!=1×2×3×...×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n

排列组合

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。下面是整理后的资料：

名称	排列	组合
定义	从n个不同的元素中取出m个元素，按一定顺序进行排序	从n个不同的元素中取出m个元素，不考虑排序
基本写法	Amn$A_n^m$	Cmn$C_n^m$
计算公式	Amn=n(n−1)...(n−m+1)$A_n^m=n(n-1)...(n-m+1)$, Amn=n!m!$A_n^m=\frac{n!}{m!}$， Ann=n!$A_n^n=n!$, A0n=1$A_n^0=1$	Cmn=n(n−1)...(n−m+1)m!$C_n^m=\frac{n(n-1)...(n-m+1)}{m!}$， Cmn=n!m!(n−m)!$C_n^m=\frac{n!}{m!(n-m)!}$, C0n=1$C_n^0=1$，Cnn=1$C_n^n=1$
关系	Amn=Cmn×Amm$A_n^m=C_n^m\times A_m^m$	Cmn=AmnAmm$C_n^m=\frac{A_n^m}{A_m^m}$
性质	Amn=n×Am−1n−1$A_n^m=n\times A_{n-1}^{m-1}$	Cmn=Cmn−m$C_n^m=C_{n-m}^m$, Cmn+1=Cmn+Cm−1n$C_{n+1}^m=C_n^m+C_n^{m-1}$

实现代码

阶乘

    /**
     * 非递归版阶乘
     * @param n
     * @return
     */
    public int factorial(int n){
        if(n==0){
            return 1;
        }else{
            int result=1;
            for(int i=1;i<=n;i++){
                result*=i;
            }
            return result;
        }
    }

    /**
     * 递归版阶乘
     * @param n
     * @return
     */
    public int factorial(int n){
        if(n==0){
            return 1;
        }else{
            return n*factorial(n-1);
        }
    }

排列组合

    /**
     * 排列
     * @param m 上标
     * @param n 下标
     * @return
     */
    public int permutation(int m,int n){
        if(n==0){
            return 1;
        }
        int result=1;
        for(int k=n;k>=n-m+1;k--){
            result*=k;
        }
        return result;
    }

    /**
     * 组合
     * @param m 上标
     * @param n 下标
     * @return
     */
    public int combination(int m,int n){
        return permutation(m,n)/permutation(m,m);
    }