排列
-
从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个