集合元素的排列与组合

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++;
    }
}