排列

从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 种
```
    {上等，中等，下等}
    {上等，下等，中等}
    {中等，上等，下等}
    {中等，下等，上等}
    {下等，上等，中等}
    {下等，中等，上等}
```
排列可以穷举出随机变量取值的所有可能性, 所以他在概率中有很大的作用, 比如用于生成这个变量的概率分布

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

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

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

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

排列

排列

排列

CATALOG

FEATURED TAGS