集合元素的排列与组合

最近因为算法考试，一直就是有空闲了刷刷题。 刷的题多了，也就发现很多基础算法在一些较复杂的题中都有应用，比如这篇文章中将要提到的排列和组合。

排列

排列，一般地，从m个不同元素中取出n（n≤m）个元素，按照一定的顺序排成一列，叫做从m个元素中取出n个元素的一个排列(permutation)。

组合

组合，一般地，从m个不同的元素中，任取n（n≤m）个元素为一组，叫作从m个不同元素中取出n个元素的一个组合。

区别

以上两个概念在高中数学中就学习，此处就不过多的阐述。 唯一强调一下二者的差异，排列是有序的，组合是无序的

代码实现样例

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;

/**
 * 排列与组合的基本算法
 */
public class ArrangeAndCombination {

    private static int m, n, COUNT;

    /**
     * 测试入口
     */
    public static void main(String[] args) {
        m = 10;
        n = 3;

        // 从10个元素中取三个元素有多少种取法？
        COUNT = 0;
        nCm(1, new HashSet<>());
        System.out.println("=== 组合 ===");
        System.out.println(COUNT);

        // 从10个元素中取三个并排序有多少种情况？
        COUNT = 0;
        nAm(new ArrayList<>());
        System.out.println("=== 排列 ===");
        System.out.println(COUNT);
    }

    /**
     * 组合算法
     * @param start 元素选择的起始位置
     * @param selected 已选中的元素
     */
    private static void nCm(int start, Set<Integer> selected) {
        if (selected.size() == n) { // 已选中的数量满足要求，打印结果并退出函数
            printResult(selected);
            return;
        }
        // 已选中的数量不足，则继续选择元素
        for (int i = 1; i <= m; i++) {
            selected.add(i); // 选择当前元素
            nCm(i + 1, selected); // 下一个元素的选择从当前元素的下一个开始
            selected.remove(i); // 移除当前元素
        }
    }

    /**
     * 排列算法
     * @param selected 已选中的元素
     */
    private static void nAm(List<Integer> selected) {
        if (selected.size() == n) { // 已选中的数量满足要求，打印结果并退出函数
            printResult(selected);
            return;
        }
        // 已选中的数量不足，则继续选择元素
        for (int i = 1; i <= m; i++) {
            if (!selected.contains(i)) { // 已选中的元素不能再次选择
                selected.add(i); // 选中当前元素
                nAm(selected); // 选择下一个元素
                selected.remove((Object) i); // 移除当前元素。注意List#remove(Object)才是移除元素的函数，变量i要强转
            }
        }
    }

    /**
     * 打印结果并计数
     * @param selected 已选中的元素
     */
    private static void printResult(Collection<Integer> selected) {
        StringBuilder sb = new StringBuilder();
        selected.forEach(x -> sb.append(",").append(x));
        System.out.println(sb.substring(1)); // 移除第一个,号
        COUNT++;
    }
}

原文：https://www.jeremysong.cn/cn/arrange-and-combination/

欢迎关注我的公众号“须弥零一”，更多技术文章第一时间推送。