n时,称为全排列。Р例如:从A,B,C,D中有序选取两个字母,则有12种选择。?AB AC AD BA BC BD CA CB CD DA DB DC?P (4,2)=12.Р定理:p(n,r)=n!/(n-r)!Р例题:从n个不同元素中选取r个元素围成一个圆。求选取的方案总数。? 解:从n个不同元素中选取r个元素选取的方案总数为p(n,r).? a1—ar为其中一组解。?将其变换,a2-ar,a1;a3-ar,a1,a2;….共有r个排列。但是这n个排列对一个圆。所以题目中所求方案为p/rР组合Р从n个不同元素中,选取r个元素而不考虑其次序,成为从n个中取r个的组合,记为c(n,r).?例:从(a,b,c,d)中选取出2个元素的组合,则有如下情况:?(a,b)(a,c) (a,d) (b,c) (b,d) (c,d)?记作 c(4,2)=6;РC(n,r)=p(n,r)/r!=n!/r!(n-r)!Р例题1如图所示的棋盘,若从左下角走到右上角,并且规定只能向上想右走,问共多少种方案?Р解题思路:?左→右 4步?下→上 3步?无论怎么选择均为右4+上3。?0—向右走1—向上走?所以可以走法可以看作由01组?成的字符串?即所求方案数为4个0和3个1组成的?7位字符串的个数。?C(7,4)=?Р排列组合生成算法РR-排列生成算法:? 采用回溯法生成从n中选r个元素的所有排列情况:? n个元素用1,2,…,n来表示? 函数done递归的层数i表示当前正在生成排列中第i个位置的数。? 函数done(i)执行时,首先判断j是否在该排列以前的几个位置上出现过,若出现则说明j不可能出现在当前位置上,此时j值增1重复以上判断,j=n时回溯;若j没有在该排列以前的位置上出现,则该位置上的值就是j,后判断递归的层数i与r的值是否相等。若i=r,输出一个新的排列并回溯。若i<r,则继续进行递归。
全文预览
