组合

组合（combination）是一个数学名词。一般地，从n个不同的元素中，任取m（m≤n）个元素为一组，叫作从n个不同元素中取出m个元素的一个组合。我们把有关求组合的个数的问题叫作组合问题。

对于所有 m 取值的组合之全集合，我们可以叫作全组合（All Combination）。例如对于集合{1, 2, 3}而言，全组合就是{空集, {1}, {2}, {3}, {1, 2}, {1,3} {2, 3}, {1, 2, 3}}。

如何安排世界杯赛程

想让全部的 32 支球队都和其他球队进行一次主客场的比赛.

自己不可能和自己比赛，不可重复的排列中，主场球队有 32 种选择，而客场球队有 31 种选择。那么一共要进行多少场比赛呢？很简单，就是 32x31=992 场！

在实际情况中,赛程设计并没有这样做.

这就是为什么要将所有 32 支队伍分成 8 个小组先进行小组赛的原因。一旦分成小组，每个小组的赛事就是 (4x3)/2=6 场。所有小组赛就是 6x8=48 场。

加上在 16 强阶段开始采取淘汰制，两两淘汰，所以需要 8+4+2+2=16 场淘汰赛（最后一次加 2 是因为还有 3、4 名的决赛），那么整个世界杯决赛阶段就是 48+16=64 场比赛。

这两两配对比赛的场次，我是如何计算出来的？让我引出今天的概念，组合（Combination）。

让计算机来组合队伍

/*
    * @Description:  使用函数的递归（嵌套）调用，找出所有可能的队伍组合
    * @param teams-目前还剩多少队伍没有参与组合，result-保存当前已经组合的队伍
    * @return void
    */
  let teams = ["t1", "t2", "t3"];
  combine(teams,[],2)


   function combine(teams,result,m) {
    // 挑选完了m个元素，输出结果
    if (result.length == m) {
       console.log(result)
      return;
    }

    for (let i = 0; i < teams.length; i++) {
      // 从剩下的队伍中，选择一队，加入结果
      let newResult = [].concat(result)
      newResult.push(teams[i]);

      // 只考虑当前选择之后的所有队伍
      let rest_teams = teams.slice(i + 1, teams.length)

      // 递归调用，对于剩余的队伍继续生成组合
      combine(rest_teams, newResult, m);
    }
  }

有没有发现,这个算法跟上一篇的密码爆破思想非常接近.

利用组合高效处理词组

每篇很长的文章，分隔成一个个的单词，然后对每个单词进行索引，便于日后的查询。但是很多时候，光有单个的单词是不够的，还要考虑多个单词所组成的词组。例如，“red bluetooth mouse”这样的词组。

常见的一种方式是多元文法。把临近的几个单词合并起来，组合一个新的词组。比如我可以把“red”和“bluetooth”合并为“red bluetooth”，还可以把“bluetooth”和“mouse”合并为“bluetooth mouse”。

如果我们只保留原文的“red bluetooth mouse”，无法将其和用户输入的“bluetooth red mouse”匹配

多个单词出现时，每次用户输入之后将词组排序,例如:

“red bluetooth mouse”，这三个词排序后就是“bluetooth,mouse,red”，而“bluetooth red mouse”排序后也是“bluetooth,mouse,red”，自然两者就能匹配上了。

设计一个抽奖系统

假设现在需要设计一个抽奖系统。需要依次从 100 个人中，抽取三等奖 10 名，二等奖 3 名和一等奖 1 名。请列出所有可能的组合，需要注意的每人最多只能被抽中 1 次。

• 思路1: 先运行combine(100, 14)，对每个结果运行combine(14, 10)，再对每个更新的结果运行combine(4, 3)。

• 思路2 : 从100人中选10人得3等奖，combine(100, 10);再从剩下90人中选3人的3等奖，combine(90, 3);再从剩下87人中选1人得1等奖， combine(87, 1)

这个数值太大,js计算不过来

微信公众号

本文链接：