程序员的数学基础课
黄申
LinkedIn资深数据科学家
立即订阅
23478 人已学习
课程目录
已完结 57 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 作为程序员,为什么你应该学好数学?
免费
导读 (1讲)
导读:程序员应该怎么学数学?
基础思想篇 (18讲)
01 | 二进制:不了解计算机的源头,你学什么编程
02 | 余数:原来取余操作本身就是个哈希函数
03 | 迭代法:不用编程语言的自带函数,你会如何计算平方根?
04 | 数学归纳法:如何用数学归纳提升代码的运行效率?
05 | 递归(上):泛化数学归纳,如何将复杂问题简单化?
06 | 递归(下):分而治之,从归并排序到MapReduce
07 | 排列:如何让计算机学会“田忌赛马”?
08 | 组合:如何让计算机安排世界杯的赛程?
09 | 动态规划(上):如何实现基于编辑距离的查询推荐?
10 | 动态规划(下):如何求得状态转移方程并进行编程实现?
11 | 树的深度优先搜索(上):如何才能高效率地查字典?
12 | 树的深度优先搜索(下):如何才能高效率地查字典?
13 | 树的广度优先搜索(上):人际关系的六度理论是真的吗?
14 | 树的广度优先搜索(下):为什么双向广度优先搜索的效率更高?
15 | 从树到图:如何让计算机学会看地图?
16 | 时间和空间复杂度(上):优化性能是否只是“纸上谈兵”?
17 | 时间和空间复杂度(下):如何使用六个法则进行复杂度分析?
18 | 总结课:数据结构、编程语句和基础算法体现了哪些数学思想?
概率统计篇 (14讲)
19 | 概率和统计:编程为什么需要概率和统计?
20 | 概率基础(上):一篇文章帮你理解随机变量、概率分布和期望值
21 | 概率基础(下):联合概率、条件概率和贝叶斯法则,这些概率公式究竟能做什么?
22 | 朴素贝叶斯:如何让计算机学会自动分类?
23 | 文本分类:如何区分特定类型的新闻?
24 | 语言模型:如何使用链式法则和马尔科夫假设简化概率模型?
25 | 马尔科夫模型:从PageRank到语音识别,背后是什么模型在支撑?
26 | 信息熵:如何通过几个问题,测出你对应的武侠人物?
27 | 决策树:信息增益、增益比率和基尼指数的运用
28 | 熵、信息增益和卡方:如何寻找关键特征?
29 | 归一化和标准化:各种特征如何综合才是最合理的?
30 | 统计意义(上):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
31 | 统计意义(下):如何通过显著性检验,判断你的A/B测试结果是不是巧合?
32 | 概率统计篇答疑和总结:为什么会有欠拟合和过拟合?
线性代数篇 (13讲)
33 | 线性代数:线性代数到底都讲了些什么?
34 | 向量空间模型:如何让计算机理解现实事物之间的关系?
35 | 文本检索:如何让计算机处理自然语言?
36 | 文本聚类:如何过滤冗余的新闻?
37 | 矩阵(上):如何使用矩阵操作进行PageRank计算?
38 | 矩阵(下):如何使用矩阵操作进行协同过滤推荐?
39 | 线性回归(上):如何使用高斯消元求解线性方程组?
40 | 线性回归(中):如何使用最小二乘法进行直线拟合?
41 | 线性回归(下):如何使用最小二乘法进行效果验证?
42 | PCA主成分分析(上):如何利用协方差矩阵来降维?
43 | PCA主成分分析(下):为什么要计算协方差矩阵的特征值和特征向量?
44 | 奇异值分解:如何挖掘潜在的语义关系?
45 | 线性代数篇答疑和总结:矩阵乘法的几何意义是什么?
综合应用篇 (6讲)
46 | 缓存系统:如何通过哈希表和队列实现高效访问?
47 | 搜索引擎(上):如何通过倒排索引和向量空间模型,打造一个简单的搜索引擎?
48 | 搜索引擎(下):如何通过查询的分类,让电商平台的搜索结果更相关?
49 | 推荐系统(上):如何实现基于相似度的协同过滤?
50 | 推荐系统(下):如何通过SVD分析用户和物品的矩阵?
51 | 综合应用篇答疑和总结:如何进行个性化用户画像的设计?
加餐 (3讲)
数学专栏课外加餐(一) | 我们为什么需要反码和补码?
数学专栏课外加餐(二) | 位操作的三个应用实例
数学专栏课外加餐(三):程序员需要读哪些数学书?
结束语 (1讲)
结束语 | 从数学到编程,本身就是一个很长的链条
程序员的数学基础课
登录|注册

07 | 排列:如何让计算机学会“田忌赛马”?

黄申 2018-12-28
你好,我是黄申。
“田忌赛马”的故事我想你肯定听过吧?田忌是齐国有名的将领,他常常和齐王赛马,可是总是败下阵来,心中非常不悦。孙膑想帮田忌一把。他把这些马分为上、中、下三等。他让田忌用自己的下等马来应战齐王的上等马,用上等马应战齐王的中等马,用中等马应战齐王的下等马。三场比赛结束后,田忌只输了第一场,赢了后面两场,最终赢得与齐王的整场比赛。
孙膑每次都从田忌的马匹中挑选出一匹,一共进行三次,排列出战的顺序。是不是感觉这个过程很熟悉?这其实就是数学中的排列过程。
我们初高中的时候,都学过排列,它的概念是这么说的:从 n 个不同的元素中取出 m(1≤m≤n)个不同的元素,按照一定的顺序排成一列,这个过程就叫排列(Permutation)。当 m=n 这种特殊情况出现的时候,比如说,在田忌赛马的故事中,田忌的三匹马必须全部出战,这就是全排列(All Permutation)。
如果选择出的这 m 个元素可以有重复的,这样的排列就是为重复排列(Permutation with Repetition),否则就是不重复排列(Permutation without Repetition)。
看出来没有?这其实是一个树状结构。从树的根结点到叶子结点,每种路径都是一种排列。有多少个叶子结点就有多少种全排列。从图中我们可以看出,最终叶子结点的数量是 3x2x1=6,所以最终排列的数量为 6。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《程序员的数学基础课》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(54)

  • alic
    password = 'bacdce'
    classes = ['a', 'b', 'c', 'd', 'e']

    def get_password(n, result = ''):
        if n == 0:
            if result == password:
                print(password)
        else:
            for i in classes:
                new_result = copy.copy(result)
                new_result = new_result + i
                get_password(n - 1, new_result)

    get_password(6)

    作者回复: 可以的👍

    2018-12-28
    1
    16
  • qinggeouye
    python
    一、田忌和齐王双方都随机选择马匹出战顺序
    import copy
    # 设置齐王的马跑完所需时间
    q_horses_time = {"q1": 1.0, "q2": 2.0, "q3": 3.0}
    # 设置田忌的马跑完所需时间
    t_horses_time = {"t1": 1.5, "t2": 2.5, "t3": 3.5}
    # 双方均随机选择出战的马匹

    q_horses = ["q1", "q2", "q3"]
    t_horses = ["t1", "t2", "t3"]

    def permutation(horses, result=None, all_results=None):
        """
        使用函数的递归(嵌套)调用,找出所有可能的马匹出战顺序
        :param all_results: 马匹出战顺序的所有排列(全排列)
        :param horses: 目前还剩多少马没有出战
        :param result: 保存当前已经出战的马匹及顺序(其中一种排列)
        :return:
        """
        if result is None:
            result = []
        if all_results is None:
            all_results = []

        # 所有马匹都已经出战,返回出战顺序
        if len(horses) == 0:
            all_results.append(result)
            return

        for k in range(len(horses)):
            # 从剩下的未出战马匹中 选择一匹 加入结果
            new_result = copy.copy(result)
            new_result.append(horses[k])
            # 将已选择的马匹从未出战的列表中移除
            rest_horses = copy.copy(horses)
            rest_horses.pop(k)
            # 递归调用 对于剩余的马匹继续生成排列
            permutation(rest_horses, new_result, all_results)
        return all_results


    def compare(t, q):
        t_won_cnt = 0
        for m in range(len(t)):
            print(str(t_horses_time.get(t[m])) + ',' + str(q_horses_time.get(q[m])))
            if t_horses_time.get(t[m]) < q_horses_time.get(q[m]):
                t_won_cnt = t_won_cnt + 1
        if t_won_cnt > len(t)//2:
            print("田忌获胜!")
        else:
            print("齐王获胜!")

    if __name__ == '__main__':
        # 双方均随机安排马匹出战,田忌获胜的概率仍为 1/6
        t_results = permutation(t_horses)
        q_results = permutation(q_horses)
        print(t_results)
        print(q_results)
        for i in range(len(t_results)):
            for j in range(len(q_results)):
                compare(t_results[i], q_results[j])
    2019-02-08
    5
  • 菩提
    交作业:
    public class L7_2 {

    public static void calLetterList(ArrayList<String> l, ArrayList<String> result) {
    if (result.size() == l.size()) {
    System.out.println(result);
    return;
    }

    for (String letter : l) {
    ArrayList<String> newResult = (ArrayList<String>) result.clone();
    newResult.add(letter);
    calLetterList(l, newResult);
    }
    }

    public static void main(String[] args) {
    ArrayList<String> l = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"));
    calLetterList(l, new ArrayList<>());
    }

    }

    作者回复: 很赞

    2018-12-30
    5
  • Joe
    C++形式交作业,好像用list数据结果会方便一点。
    /** permutaion: 排列。
     * 从n个数中选出m个数的方式,若不考虑顺序Cn(m),若考虑顺序An(m)
     */

    /* 问题:密码排列
     * 假设有一个 4 位字母密码,每位密码是 a~e 之间的小写字。
     * 编写密码可能排列方式。
     */
    #include <iostream>
    #include <vector>
    using namespace std;

    class Permutation {
      private:
      int resultCount_ = 0;

      public:
      /** Details: 根据输入字母列表,获得所有的排列方式。
       * params: result- 当前排列形式, candidate- 未排列字母表。
       * return: null
       */
      void breakPassword(vector<string> result, vector<string> candidate) {
        int len = candidate.size();
        if (0 == len) {
          // 无字母剩余,输出排列结果
          outputResult(result);
          resultCount_++;
          return;
        }
        for (int i = 0; i < len; i++) {
          vector<string> resultNew;
          vector<string> candidateLeft;
          // 读取排列字母
          resultNew = result;
          resultNew.push_back(candidate[i]);
          // 获得剩余字母表
          candidateLeft = candidate;
          vector<string>::iterator it = candidateLeft.begin();
          candidateLeft.erase(it + i);
          // 递归
          breakPassword(resultNew, candidateLeft);
        }
      }
      // 输出结果
      void outputResult(vector<string> result) {
        for (unsigned int i = 0; i < result.size(); i++) {
          cout << result[i];
        }
        cout << endl;
      }
      // 获得所有可能密码总数
      int getResultCount() {
        return resultCount_;
      }
    };

    int main(void) {
      vector<string> fourAlphabetString = {"a", "b", "c", "d", "e"};
      vector<string> res;
      Permutation test;
      test.breakPassword(res, fourAlphabetString);
      cout << "可能的密码形式:";
      cout << test.getResultCount() << "种" << endl;
    }

    作者回复: c语言确实更简洁👍

    2019-01-09
    4
  • Jing
    //思考题 c#版本
    private static char[] _letters = { 'a', 'b', 'c', 'd', 'e' };
    public static void GetPassword()
    {
    string password = "abded";
    CrackPassword(password.Length, new StringBuilder(), password);
    }

    private static void CrackPassword(int length, StringBuilder result, string realPsd)
    {
    if (length == 0)
    {
    if (realPsd.Equals(result.ToString()))
    {
    Console.WriteLine("Your password is:" + result.ToString());
    }
    result.Length = 0;
    return;
    }
    else if (length < 0)
    {
    return;
    }
    for (int i = 0; i < _letters.Length; i++)
    {
    StringBuilder temp = new StringBuilder();
    temp.Append(result.ToString());
    temp.Append(_letters[i]);
    CrackPassword(length - 1, temp, realPsd);
    }
    }
    2019-04-05
    2
  • 瓶子🍼
    var chars = ['a', 'b', 'c', 'd', 'e']
    var result = []

    function getPassword(passwordChars, num, password) {
        if (num == 0) {
            return result.push(password)
        } else {
            for (var i = 0; i < passwordChars.length; i++) {
                getPassword(passwordChars, num - 1, password + passwordChars[i])
            }
        }
    }
    getPassword(chars, 4, '')

    作者回复: 代码很简洁

    2019-01-09
    2
  • 文刂 氵共 超
    思考题 - 递归思想-C++
    #include <iostream>
    #include<string>

    using std::string;
    using namespace std;

    void BreakPassword( string Words, int PasswordLen, string result)
    {
    if (result.length() == PasswordLen)
    {
    //C++中string类型不能直接输出,需加头问题#include<string>,不能用#include<string.h>
    cout << result << " ";
    return;
    }

    for (int i = 0; i < Words.length(); ++i)
    {
    string newResult = result;
    newResult.insert( newResult.end(), Words[i] );
    BreakPassword(Words, PasswordLen, newResult);
    }
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    int passwordLen = 4;
    string words("abcde");
    string result = "";

    BreakPassword(words, passwordLen, result);

    return 0;
    }
    2018-12-28
    2
  • alic
    怎么用递归来求?

    作者回复: 具体是指哪道题目?

    2018-12-28
    2
  • 毛毛
    最笨的方法,一个数组A容纳a~e,四个for循环遍历数组A,拼成一个新一维数组B,多个数组B再拼成二维数组,就是最后结果。

    作者回复: 密码短的话,循环嵌套就可以了。如果密码很长,或者长度是满足某种条件的,就需要递归

    2018-12-28
    2
  • QFann
    交作业
    /**
         *
         * @param password 密码组成元素
         * @param result 密码可能组合
         * @param number 密码个数
         */
        public static void getPassword(ArrayList<String> password,ArrayList<String> result,int number){

            if(result.size() >= number ){
                System.out.println(result);
                return;
            }

            for (int i = 0;i < password.size() ; i++){
                ArrayList<String> new_result = (ArrayList<String>) result.clone();
                new_result.add(password.get(i));
                getPassword(password,new_result,number);

            }

        }
    2019-04-29
    1
  • suiyueranzly
    来补作业了,老师
    -------------------------代码-----------------------------------
     /**
         * 排列
         *
         * @param passwords 待排列的字符
         * @param results 排列的结果
         ***/
        public void range(ArrayList<String> passwords, ArrayList<String> results) {
            //如果为空则不需要排列
            if (passwords.isEmpty()) {

                String collect = String.join("", results);

                System.out.print(collect + "\t");

            }

            for (int i = 0; i < passwords.size(); i++) {

                String password = passwords.get(i);

                ArrayList<String> newResult = (ArrayList<String>) results.clone();

                ArrayList<String> newPassword = (ArrayList<String>) passwords.clone();

                newResult.add(password);

                newPassword.remove(i);

                range(newPassword,newResult);

            }
        }

    作者回复: 逻辑清晰

    2019-01-07
    1
  • 风轨
    public class Crack {
        static char[] pwdcs = new char[] { 'a', 'b', 'c', 'd', 'e' };
        static String[] crack(int len) {
            String[] ps = new String[] { "" };
            while (len-- > 0) {
                String[] nps = new String[ps.length * pwdcs.length];
                int nsbsi = 0;
                for (String pwd : ps) {
                    for (char c : pwdcs) {
                        nps[nsbsi++] = pwd + c;
                    }
                }
                ps = nps;
            }
            return ps;
        }
        
        
        public static void main(String[] args) {
            String[] pwds = crack(4);
            for (String pwd : pwds) {
                System.out.println(pwd);
            }
            /**
             * 输出结果
             * aaaa
             * aaab
             * aaac
             * aaad
             * aaae
             * aaba
             * ....
             * 省略517行
             * ....
             * eeed
             * eeee
             *
             */
        }
    }
    2018-12-28
    1
  • 石佳佳_Gemtra
    对于 n 个元素里取出 m(0<m≤n) 个元素的重复排列数量是 nxnxnx…xn,也就是 n^m。
    2018-12-28
    1
  • 半湖思絮
    ```
    public class Lesson7_3 {

        private static final String[] charArr = {"a", "b", "c", "d", "e"};

        public static void permutate(int bit, String[] charArr, List<String> hasList) {
            if (bit == 0) {
                System.out.println(hasList);
            } else {
                int size = charArr.length;
                for (int i = 0; i < size; i++) {
                    List<String> tmpHas = new ArrayList<>(hasList);
                    tmpHas.add(charArr[i]);
                    permutate(bit - 1, charArr, tmpHas);
                }
            }
        }

        public static void main(String[] args) {
            permutate(4, charArr, new ArrayList<>());
        }
    }
    ```
    2019-12-10
  • teddytyy
    破解密码的排列应该是可重复的,最终排列数是n^m,而非n!

    作者回复: 对,取决于密码的每一位是否可以重用

    2019-12-05
  • teddytyy
    void brutalSolve(vector<char> factor, int num, vector<char> result, vector<char> passwd){
        if (num==0) {
            for(int i = 0; i < result.size(); i++) {
                if(result[i] != passwd[i]) return;
                cout<<result;
            }
        }
        num--;
        for (int i=0; i<factor.size(); i++) {
            result.pushback(factor[i]);
            brutalSolve(factor, num, result, passwd);
        }
    }
    2019-12-05
  • Geek_89b79a
    from copy import copy
    password = 'dftegaukfhsjndfgaweyjukfhcjnarieukvfyreaufyyhweaicuaru'
    a = [chr(97+i) for i in range(26)]
    def crack(length, result=""):
        if result != password[0:len(result)]:
            return
        if length == 0:
            if result == password:
                print(result)
                return
        else:
            for i in a:
                new_result = copy(result)
                new_result = new_result + i
                crack(length - 1, new_result)

    crack(len(password))
    2019-11-25
  • Vincent🌫
    205 次
    package cn.algorithm;

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;

    public class Sort02 {

        static int ttt=0;

        public static void generatePassword(ArrayList<String> source,ArrayList<String> result,int count){

            if(result != null && result.size() == 4){
                System.out.println(result);
                return;
            }

            for(int i = 0 ; i < source.size() ; i++){
                ArrayList<String> new_result = (ArrayList<String>) result.clone();
                new_result.add(source.get(i));
                ArrayList<String> rest_source = (ArrayList<String>) source.clone();
                rest_source.remove(i);
                ttt++;
                generatePassword(rest_source,new_result,count);
            }
        }

        public static void main(String[] args) {
            int count = 4;
            ArrayList<String> source = new ArrayList<String>();
            source.add("a");
            source.add("b");
            source.add("c");
            source.add("d");
            source.add("e");
            ArrayList<String> result = new ArrayList<String>();
            generatePassword(source,result,count);
            System.out.println(ttt);
        }

    }
    2019-11-15
  • 流氓汉高祖

    public static void main(String[] args) {
        
        ArrayList<String> t_horses = new ArrayList<String>(Arrays.asList("t1", "t2", "t3"));
        Lesson7_2.permutate(t_horses, new ArrayList<String>(), t_results);
        
        ArrayList<String> q_horses = new ArrayList<String>(Arrays.asList("q1", "q2", "q3"));
        Lesson7_2.permutate(q_horses, new ArrayList<String>(), q_results);
        
        System.out.println(t_results);
        System.out.println(q_results);
        System.out.println();
        
        for (int i = 0; i < t_results.size(); i++) {
          for (int j = 0; j < q_results.size(); j++) {
            Lesson7_2.compare(t_results.get(i), q_results.get(j));
          }
        }
        
      }
     

    这段代码中q_results和t_results是啥?还有就是Lesson7_2的代码怎么没有?

    作者回复: q_results表示齐王的出马顺序,t_results表示田忌的出马顺序,Lesson7_2是编辑错误,应该是Lesson7_1

    2019-11-14
  • 顾骨
    go 版本
    --------------------------------------------------------

    var letters = "abcdefghijklmnopqrstuvwxyz"

    func breakPassword(password, result string) bool {
    if len(password) == len(result) {
    if password == result {
    fmt.Println(result)
    return true
    }
    return false
    }

    for _, letter := range letters {
    netResult := result
    netResult += string(letter)
    if found := breakPassword(password, netResult); found {
    return true
    }
    }
    return false
    }

    func main(){
        out := breakPassword("jgfdgh", "") // output: true
        out = breakPassword("zzzz", "")// output: true
        out = breakPassword("1zzz", "") // output: false
    }

    2019-11-12
收起评论
54
返回
顶部