集合元素的排列与组合

须弥零一

共 1167字,需浏览 3分钟

 ·

2022-06-08 18:03


须弥零一

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

排列

排列,一般地,从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(+ 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(-> sb.append(",").append(x));
        System.out.println(sb.substring(1)); // 移除第一个,号
        COUNT++;
    }
}

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

---- END ----



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

浏览 123
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报