排列

排列

Posted by limantang on July 24, 2019

排列

  1. 从n个不同的元素中取出m(1 <= m <= n) 个不同的元素, 按照一定的顺序排成一列, 这个过程叫排列

    当m = n的时候就是全排列

    如果选出的m个元素可以有重复的那就是重复排列,否则就是不重复排列

    推广一下结论:

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

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

    可以用数学归纳法正面上述两点

    田忌赛马就是很好的例子

        上等-中等-下等
             下等-中等
           
        中等-上等-下等
             下等-上等
           
        下等-上等-中等
             中等-上等
           
        3种 * 2种 * 1种
    

    其实排列的过程也可看做是生成树状结构的过程, 从树的根节点到叶子节点, 每一种路径都是一种排列有多少个叶子节点就有多少种排列, 上图就是 : 3 * 2 * 1 = 6 种

        {上等,中等,下等}
        {上等,下等,中等}
        {中等,上等,下等}
        {中等,下等,上等}
        {下等,上等,中等}
        {下等,中等,上等}
    
  2. 排列可以穷举出随机变量取值的所有可能性, 所以他在概率中有很大的作用, 比如用于生成这个变量的概率分布

    排列在计算机领域也有很多应用场景, 比如暴力破解密码

    有时候黑客不需要拿到你的密码, 而是通过猜, 猜就是列举各种可能性然后去试

    假如一个密码是由纯英文字母组成的, 那么每位就有52种选择(大小写区分), 如果是m位的密码,那就是52^m种

    也就是说从n中取出m个元素的可重复全排列总数量就是n^m个