程序设计比赛基础-排列组合

所谓排列问题,指的是求出根据已之条件能作出的不同排列种数。从n个不同元素中有次序的选取r(1<=r<=n)个按次序排列。叫做从n个不同元素中取出r个元素的排列。当r<n是称作选排列。其排列数计做p(n,r);r=n时称作全排列,记为p(n,n)显然p(n,n)=n!。
生成排列的方法有多种,下面介绍一种较高效按字典顺序产生排列的方法。
题:有N本不同的书摆放在书架上,设其编号为1,2,3……N编程求解这N本书的不同摆放方案和摆放方案总数。
[分析]问题的本质是求解N个元素的全排列,以N=3为例。人工可以得到按字典序排列方案如下:123,132,213,231,312.321.因此发现,每一个排列方式总是在其前一个排列的基础上通过顺序逆转而得到。由此我们得到给定一个排列P1,P2,P3……Pn之后生成下一个排列的算法如下:
S1:求满足关系式P(J-I)<P(J)的J的最大值,记为I
即 I=max{J|P(J-I)<P(J)}
S2:求满足关系式P(I-1)<P(K)的K的最大值,记为J
即J=max{k|P(I-1)<P(K)}
S3:将P(I-1)和P(J)交换得P(1),P(2)…P(i)…P(n)
S4:将P(1)P(2)…P(n)的 P(I)…P(n)部分倒置。
例:设P(1)P(2)P(3)P(4)=3421则有
(1) I=max{JIP(J-1)<P(J)}=2
(2) J=max{klP(I-1)<P(K)}=2
(3) P(1)与P(2)交换得到排列4321,4321中的321顺序逆转就可得到下一个排列。
按照上述排列方法设计算法,可得到问题的原程序为:(Pascal)

[php]
Program P; {排列问题源程序}
Const maxn=10;
Var Plan:array[l..maxn]of byte; {存储排列方案}
n,total:integer;
show,stop:Boolean;
i,j:integer;
Procedure Print;{输出方案}
Var K:integer;
begin
inc(total) ;
write(‘(’,total:5,’):’) ;
for i:=1 to n do write(plan[i]:5) ;
writeln;
end;
procedure findi;
begin
i:=n;
while(i>1)and(plan[i]<plan[i-1])do dec(i)
end;
procedure findj;
begih
j:=n;
while plan[j]<=plan[i-1]do dec(j)
end;
procedure change; {顺序转换,产生下一个排列}
var k,h:integer;
begin
k:=plan[i-1] ;
plan[j-1]:=plan[j] ;
plan[j]:=k;
for k:=I to (n+i)div z do begin
h:=plan[k] ;
plan[k]:=plan[n+i-k] ;
plan[n+i-k]:=h
end
end;
begin
write(‘please enter n:’) ;
readln(n) ;
total:=0;
for i:=1 to n do plan[i]:=i;
print;
repeat findi;
if i>1 then begin
findj;
change;
print;
end;
until i<=1;
writeln(‘total ways=’,total)
end.
[/php]

个人总结:
一列有n个关键字的序列按关键字信息,由小到大排列,求下一个排列的方法为:
P[i-1]<p[i] 找到使之成立的I 的最大值maxi.
P[maxi-1]<p[j] 找到使之成立的j 的最大值maxj.
交换p[maxi-1]与p[maxj],将p[maxi]~p[n]倒置

所谓组合问题,指的是求出根据已知条件所能作出的不同组合的个数。从n个不同元素中,取出r元素而不考虑其先后次序时,称为从n个元素中取出r个元素的组合其组合记为C(n,r)。下面分析一下组合生成的过程,先看如下一个例子。
题:有N本不同的书摆在书架下,设其编号分别为1,2…n,要从其中取出R本书,编程求解其不同的组合方案和方案数。
[分析]问题的本质是求解从N个元素中取出R个元素的组合方案和组合数,首先观察一个具体的例子,设N=6,R=3,可以得到其选法为:
(1) 1 2 3 (2) 1 2 4 (3) 1 2 5 (4) 1 2 6
(5) 1 3 4 (6) 1 3 5 (7) 1 3 6
(8) 1 4 5 (9) 1 4 6
(10) 1 5 6
(11) 2 3 4 (12) 2 3 5 (13) 2 3 6
(14) 2 4 5 (15) 2 4 6
(16) 2 5 6
(17) 3 4 5 (18) 3 4 6
(19)3 5 6
(20)4 5 6
从上面的组合的生成过程中可以看出如下规律:
(1)最后一位数最大可达N,倒数第二位最大可达N-1,依次类推……倒数第K位(K<=N)不得超过N-K+1,因此,若R个元素的组合用C(1)C(2)……C(R)来表示,且设定C(1)<C(2)<……<C(R),则有C(R)<=N-R+I,I=1,2,3,……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)+1,……,C(R)=C(R)+1。
由此,可以得到从一个组合到其下一个组合的算法如下:
S1:求满足不等式C(I)<N-R+I的最大的数I。即:I=max{J|C(J)<N-R+J}
S2:C(I)=C(I)+1
S3:从I+1位开始修改:C(J)=C(J-1)+1;J=I+1,I=2,…,R.
下面给出从N个元素中取出R个元素所得的组合方案及其组合数的程序:

[php]
Program C;
Const maxn=10;
Var plan :array[1..maxn]of byte;
n,r,total:inteyer;
i,j:inttyer;
Procedure Print;
Begin
Inc(total);
Write(‘(‘,total:5,);’);
For i:=1 to r do write(plan[i]:5);
writeln;
end;
begin
write(‘please enter n and r:’);
readln(n,r);
total:=0;
for i:=1 to r do plan[i]:=i;
print;
repeat.
i:=r;
while(i>0)and(plan[i]=n+i-r)dc dec(i);
if i>0 then begin
inc(plan[i]);
for j:=i+1 to r do
plan[i]:=plan[j-1]+1;
print
end;
until i=0;
writeln(‘total ways=’,total)
end.
[/php]

Leave A Comment

Please be polite. We appreciate that. Your email address will not be published and required fields are marked