JAVA实现排列组合[通俗易懂]

大家好，欢迎来到IT知识分享网。

• 排列的计算公式：
  

• 组合的计算公式
  

• 阶乘的实现

    /** * 计算阶乘数，即n! = n * (n-1) * ... * 2 * 1 * @param n * @return */
    private static long factorial(int n) {
        long sum = 1;
        while( n > 0 ) {
            sum = sum * n--;
        }
        return sum;
    }

• 排列的实现方式

    /** * 排列计算公式A<sup>m</sup><sub>n</sub> = n!/(n - m)! * @param m * @param n * @return */
    public static long arrangement(int m, int n) {
        return m <= n ? factorial(n) / factorial(n - m) : 0;
    }

• 组合的实现方式

    /** * 组合计算公式C<sup>m</sup><sub>n</sub> = n! / (m! * (n - m)!) * @param m * @param n * @return */
    public static long combination(int m, int n) {
        return m <= n ? factorial(n) / (factorial(m) * factorial((n - m))) : 0;
    }

• 优化排列组合

    //******优化排列组合*******//
    /** * 替换阶乘的另一种方式(从n开始递减相乘，乘m个数) * @param n * @param m * @return */
    private static long factorialSec(int m, int n) {
        long sum = 1;

        while(m > 0 && n > 0) {
            sum = sum * n--;
            m--;
        }
        return sum;
    }
    /** * 排列 * @param m * @param n * @return */
    public static long arrangementSec(int m, int n) {
        return m <= n ? factorialSec(m, n) : 0;
    }
    /** * 组合 * @param m * @param n * @return */
    public static long combinationSec(int m, int n) {
        if( m > n )
            return 0;
        if( m > n/2 )
        {
            m = n - m;
        }
        return factorial(m, n)/factorial(m, m);
    }
    //******优化结束******//

虽然会提高一点效率，但是用int还是容易超出，大致思路是这样，优化的代码没有详细测试

• 列举

  • 有时候，我们不仅需要知道排列或组合的数量，而且需要知道有哪些排列或组合，并列举出所有的排列或组合，人工列举工作量大而且容易出错，那么，如何利用计算机帮忙列举出所有的这些排列或组合呢？

• 排列：采用递归即可枚举出所有的排列情况，相关Java实现如下：

    /** * 排列选择（从列表中选择n个排列） * @param dataList 待选列表 * @param n 选择个数 */
    public static void arrangementSelect(String[] dataList, int n) {
        System.out.println(String.format("A(%d, %d) = %d", dataList.length, n, 
                arrangement(n, dataList.length)));
        arrangementSelect(dataList, new String[n], 0);
    }

    /** * 排列选择 * @param dataList 待选列表 * @param resultList 前面（resultIndex-1）个的排列结果 * @param resultIndex 选择索引，从0开始 */  
    private static void arrangementSelect(String[] dataList, String[] resultList, int resultIndex) {
        int resultLen = resultList.length;
        if (resultIndex >= resultLen) { // 全部选择完时，输出排列结果 
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = 0; i < dataList.length; i++) {
            // 判断待选项是否存在于排列结果中
            boolean exists = false;
            for (int j = 0; j < resultIndex; j++) {
                if (dataList[i].equals(resultList[j])) {
                    exists = true;
                    break;
                }
            }
            if (!exists) { // 排列结果不存在该项，才可选择
                resultList[resultIndex] = dataList[i];
                arrangementSelect(dataList, resultList, resultIndex + 1);
            }
        }
    }

• 组合：也是采用递归的方式列举

    /** * 组合选择（从列表中选择n个组合） * @param dataList 待选列表 * @param n 选择个数 */
    public static void combinationSelect(String[] dataList, int n) {
        System.out.println(String.format("C(%d, %d) = %d", 
                dataList.length, n, combination(dataList.length, n)));
        combinationSelect(dataList, 0, new String[n], 0);
    }

    /** * 组合选择 * @param dataList 待选列表 * @param dataIndex 待选开始索引 * @param resultList 前面（resultIndex-1）个的组合结果 * @param resultIndex 选择索引，从0开始 */
    private static void combinationSelect(String[] dataList, int dataIndex, String[] resultList, int resultIndex) {  
        int resultLen = resultList.length;
        int resultCount = resultIndex + 1;
        if (resultCount > resultLen) { // 全部选择完时，输出组合结果
            System.out.println(Arrays.asList(resultList));
            return;
        }

        // 递归选择下一个
        for (int i = dataIndex; i < dataList.length + resultCount - resultLen; i++) {
            resultList[resultIndex] = dataList[i];
            combinationSelect(dataList, i + 1, resultList, resultIndex + 1);
        }
    }

• 总结
  
  • 文章借鉴自ITeye一位大神文章，部分有修改
  • 排列组合列举的递归调用本人理解有点浅薄，未做修改，还需继续深入理解。