第三课 排列与组合

 例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？

分析：如果我们将3个人进行编号，分别为1、2、3，显然我们列出所有的排列，123，132，213，231，312，321共六种。可用循环枚举各种情况，参考程序：

program exam5;

var

    i,j,k:integer;

begin

    for I:=1 to 3 do

for j:=1 to 3 do

        for k:=1 to 3 do

        if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k);

end.

上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用循环不能解决问题。下面我们介绍一种求全排列的方法。

设当前排列为P₁ P₂ ,…,P_n，则下一个排列可按如下算法完成：

1．求满足关系式P_j-1 < P_j的J的最大值，设为I，即

I=max{j | P_j-1 < P_j , j = 2..n}

2．求满足关系式P_{i -1} < P_k的k的最大值，设为j，即

J=max{K | P_i-1 < P_k , k = 1..n}

3．P_{i -1}与P_j互换得 (P) = P₁ P₂ ,…,P_n

4．(P) = P₁ P₂ ,…, P_i-1 P_i,…, P_n部分的顺序逆转，得P₁ P₂ ,…, P_i-1 P_n P_n-1,…, P_i便是下一个排列。

例：设P₁ P₂ P₃ P₄ =3421

1．I= max{j | P_j-1 < P_j , j = 2..n} = 2

2．J=max{K | P_i-1 < P_k , k =1..n} = 2

3．P₁与P₂交换得到4321

4．4321的321部分逆转得到4123即是3421的下一个排列。

程序设计如下：

program exam5;

const

     maxn     = 100;

var   i,j,m,t : integer;

      p       : array[1..maxn] of integer;

      count   :integer;         {排列数目统计变量}

begin

    write('m:');readln(m);

    for i:=1 to m do begin p[i]:=i; write(i) end;

    writeln;

    count:=1;

    repeat

{求满足关系式P_j-1 < P_j的J的最大值，设为I}

      i:=m;

      while (i>1) and (p[i-1]>=p[i]) do dec(i);

      if i=1 then break;

   {求满足关系式P_{i -1} < P_k的k的最大值，设为j}

      j:=m;

      while (j>0) and (p[i-1]>=p[j]) do dec(j);

      if j=0 then break;

    {P_{i -1}与P_j互换得 (P) = P₁ P₂ ,…,P_m}

      t:=p[i-1];p[i-1]:=p[j];p[j]:=t;

{P_i,…, P_m的顺序逆转}

      for j:=1 to (m-i+1) div 2 do begin

          t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t

      end;

    {打印当前解}

    for i:=1 to m do write(p[i]);

    inc(count);

    writeln;

    until false;

    writeln(count)

End.

 

例6：求N个人选取M个人出来做游戏，共有多少种取法？例如：N=4，M=2时，有12，13，14，23，24，34共六种。

分析：因为组合数跟顺序的选择无关。因此对同一个组合的不同排列，只需取其最小的一个（即按从小到大排序）。因此，可以设计如下算法：

1．最后一位数最大可达N，倒数第二位数最大可达N-1，…，依此类推，倒数第K位数最大可达N-K+1。

若R个元素组合用C₁C₂ …C_R表示，且假定C₁<C₂< …<C_R, C_R<=N-R+I,  I=1,2,…,R。

2．当存在C_j<N-R+J时，其中下标的最大者设为I，即

    I=max{J | C_j<N-R+J}，则作C_i := C_i +1,与之对应的操作有

C_i+1 := C_i +1 ，C_i+2 := C_{i +1}+1 ，…. ，C_R := C_R-1 +1

 

参考程序：

program exam6;

const maxn=10;

var  i,j,n,m :integer;

    c   :array[1..maxn]of integer;      {c数组记录当前组合}

Begin

Write('n & m:'); readln(n,m);

    for i:=1 to m do begin              {初始化，建立第一个组合}

      c[i]:=i;

      write(c[i]);

    end;

    writeln;

    while c[1]<n-m+1 do begin

      j:=m;

      while (c[j]>n-m+1) and ( j>0) do dec(j);      {求I=max{J | C_j<N-R+J} }

      c[j]:=c[j]+1;

      for i:=j+1 to m do c[i]:=c[i-1]+1;                {建立下一个组合}

      for i:=1 to m do write(c[i]);writeln              {输出}

    end;

End.