组合

组合

Posted by limantang on July 27, 2019

组合

  1. 组合是从n个元素中取出m(1<=m<=n)个不同的元素, 所有的m取值的组合的全集合叫做全组合

    排列和组合的区别是排列是需要考虑顺序不同的情况

    组合不需要考虑顺序问题

    假设一种比赛是需要三支队伍同时参加比赛, 假设总共有9只队伍

    那么这9只队伍就有9 * 8 * 7种排列

    3只队伍只要赛一场, 那么就需要剔除重复的比赛

    3只队伍如果考虑顺序的前提下不同顺序算作不同的一场比赛的话, 比赛会有3 * 2 * 1场

    其实也就是3只队伍的全排列数量

    所以只赛一场的情况总数就是 9 * 8 * 7 / 3 * 2 * 1 根据上述可以总结出以下两种情况

  • n个元素取出m个元素, 可能性的数量就是n个里面取出m个元素的排列数量, 除以m个的全排列数量, (n! / (n - m)!) / m!
  • 对于全组合可能性就是 2^n种, 例如 n = 3时, 全组合就包含8种情况(包含空集)
  1. 那么编程时如何实现组合呢

    使用计算机实现全组合没有太大意思, 就是2^n种, 直接套公式就行了

讨论一下3个元素{x1, x2, x3}去2个元素的组合情况

  • 暴力做法

    1. 先实现排列代码,输出所有的排列
    2. 然后针对所有排列对其中的元素按照相同的规则排序
    3. 对排列后的排列去除重复的所剩下的就是组合
    

    优点: 符合上述的公式情况

    缺点: 效率低

  • 优化做法

    因为x1在x2前面所以, 所以包含x1的组合情况一定包含x2, 所以关于x2组合的情况就无须在考虑x2前面的元素,只需考虑x2后面的元素组合到一起即可

  1. 组合的实际应用

    实际应用的场景还是蛮多的, 例如比赛赛程安排, 自然语言处理优化

    例如搜索时输入的单词 red cat a, 包含三个单词, 这三个单词的全排列情况为6

    但是符合语义的只有一种, 实际情况是用户可能不会按照正常语义输入

    所有这个时候组合就可以实际应用

    只考虑一种组合情况, 然后按照某种规则排序, 后端系统词组和用户输入词组按照处理之后的结果进行比较即可, 减少很多耗时