田忌赛马的故事

田忌是齐国有名的将领，他常常和齐王赛马，可是总是败下阵来，心中非常不悦。孙膑想帮田忌一把。他把这些马分为上、中、下三等。他让田忌用自己的下等马来应战齐王的上等马，用上等马应战齐王的中等马，用中等马应战齐王的下等马。三场比赛结束后，田忌只输了第一场，赢了后面两场，最终赢得与齐王的整场比赛。

排列概念

从 n 个不同的元素中取出 m（1≤m≤n）个不同的元素，按照一定的顺序排成一列，这个过程就叫排列（Permutation）。

当 m=n 这种特殊情况出现的时候,这就是全排列（All Permutation）

田忌赛马的排列图

最终排列的数量

排列总数的计算 3x2x1=6

• 对于 n 个元素的全排列，所有可能的排列数量就是 nx(n-1)x(n-2)x…x2x1，也就是 n!

• 对于 n 个元素里取出m (0<m≤n) 个元素的不重复排列数量是 nx(n-1)x(n-2)x…x(n - m + 1)，也就是 n!/(n-m)!

使用代码计算田忌赛马的各种情况

// 齐王的马与速度
let q_horses_time = {
  q1: 1,
  q2: 2,
  q3: 3
}

// 田忌的马与速度
let t_horses_time = {
  t1: 1.5,
  t2: 2.5,
  t3: 3.5
}

// 他们马的名字
let q_horses = ["q1", "q2", "q3"]

let t_horses = ["t1", "t2", "t3"]


/**
  * @Description:  使用函数的递归（嵌套）调用，找出所有可能的马匹出战顺序
  * @param horses-目前还剩多少马没有出战，result-保存当前已经出战的马匹及顺序
  * @return void
  */

function permutate(horses, result) {
  // 所有马匹都已经出战，判断哪方获胜，输出结果
  if (horses.length == 0) {
    // console.log(result);
    compare(result, q_horses);
    return;
  }

  for (let i = 0; i < horses.length; i++) {
    // 从剩下的未出战马匹中，选择一匹，加入结果
    let new_result = [].concat(result)
    new_result.push(horses[i])

    // 将已选择的马匹从未出战的列表中移出
    let rest_horses = [].concat(horses);
    rest_horses.splice(i, 1)

    // 递归调用，对于剩余的马匹继续生成排列
    // 相当于自己与自己嵌套for循环,打乱顺序
    permutate(rest_horses, new_result);
  }
}


function compare(t, q) {
  // 田忌的赛马时间
  let t_won_cnt = 0;
  for (let i = 0; i < t.length; i++) {
    if (t_horses_time[t[i]] < q_horses_time[q[i]]) t_won_cnt++;
  }

  // 时间对比,本次是三局两胜
  if (t_won_cnt > (t.length / 2)) {
    console.log("田忌获胜！")
  } else {
    console.log("齐王获胜！")
  }
}

// 开始计算
permutate(t_horses, [])

田忌获胜的概率是 ¹⁄₆

暴力破解密码如何使用排列思想？

暴力破解是要把所有会出现的密码全部试一次

假设有一个 4 位字母密码，每位密码是 a～e 之间的小写字母。你能否编写一段代码，来暴力破解该密码？（提示：根据可重复排列的规律，生成所有可能的 4 位密码。）

let words = ['a','b','c','d','e']
let passwords = []

function getPassword(words,result){
  // 够4个,这个分支结束
  if(result.length == 4){
    passwords.push(result)
    console.log(result);
    return;
  }

  // 不够4个,继续拿
  for (let index = 0; index < words.length; index++) {
    let a = [].concat(words);
    let b = [].concat(result);
    b.push(a[index])
    a.splice(index,1)
    getPassword(a,b)
  }
}

getPassword(words,[])
console.log(passwords)

排列可以帮助我们生成很多可能性。由于这种特性，排列最多的用途就是穷举法，也就是，列出所有可能的情况，一个一个验证，然后看每种情况是否符合条件的解。

微信公众号

本文链接：