求P(N,M)最优运算代码,高手请进.(100分)

  • 主题发起人 主题发起人 ppqingyu
  • 开始时间 开始时间
P

ppqingyu

Unregistered / Unconfirmed
GUEST, unregistred user!
求P(N,M)运算代码。
问题分两部份
问题一:求从N个数字里面,取M个进行排列组合。不能存在重复的组合,也不能存在重复的数字,组合数字不分顺序。(实际上就是乐透型彩票的组合条件一样)这个问题提问的人太多,回答的人也太多。我曾试过不少,大同小导,有的人用循环,也有人用递归。但是用循环的话,事前必须知道N,M的值。用递归,但递归占用内存奇大,40选8就可以把我的512M内存撑爆(可能代码有点问题吧),更不用说超出100选M的了(纯粹求最优代码),而且运行的时间也比较高,少则要好几分钟,多的就不要说了。有一个高人叫creation-zy,他的代码运算奇快,36选7居然在10秒内完成,我试了,居然在不到3秒,但是我看不明白,更不用说改了。好像他的代码只能用自然数。但是我用的是TStringList存储数据。而且我的数据不一定全部都有是1,2,3等自然数,还有可能是ABC之然的字符串,那个N只能是以StringList.String[N]了。我的N可能过大,例如100选6,那样的话,1G的内存都可能不够,所以中途必须将一部分组合出来的代码写入文件,清空TStringList.我贴上creation-zy的代码,大家看能不能改成我要求的。当然希望有更好的代码贴上来,但是以前那些已经发表过的不成熟的代码就免了.
穷举组合算法 By creation_zy
注: TBuffer类见 http://www.delphibbs.com/delphibbs/dispq.asp?lid=968511

function CNMNum(N,M:Integer):Double;
var
i:Integer;
begin
Result:=1;
for i:=N-M+1 to N do
Result:=Result*i;
for i:=2 to M do
Result:=Result/i;
end;
function CNM(const N,M:Integer;out Count:Integer):String;
var
A,R:array of Integer;
i:Integer;
Buf:TBuffer;
StartTime:DWord;
TotalCount:Double;
procedure Gen(Level:Integer);
var
j,mm,s:Integer;
mstr:String;
begin
if Level=M then
begin
mstr:='';
for j:=0 to M-1 do
mstr:=mstr+IntToStr(R[j])+' ';
mstr:=mstr+#13#10;
Buf.WriteBuf(@mstr[1],Length(mstr));
Inc(Count);
if Count mod 1000=0 then
begin
Form1.Caption:=Format('%.3f%% %.7d Time: %.2fs Buffer Size: %.2fM',
[100*Count/TotalCount,Count,(GetTickCount-StartTime)/1000,
Buf.ContentSize/(1024*1024)]);
Application.ProcessMessages;
end;
exit;
end;
if Level=0 then
s:=0
else
s:=R[Level-1]+1;
for j:=s to N-M+Level do
begin
R[Level]:=j;
Gen(Level+1);
end;
end;
begin
Result:='';
Count:=0;
if (N<1) or (M>N) or (M<1) then
exit;
Buf:=TBuffer.Create(0,1024*1024);
SetLength(A,N);
SetLength(R,M);
TotalCount:=CNMNum(N,M);
StartTime:=GetTickCount;
for i:=0 to N-1 do
A:=i;
Gen(0);
Result:=Buf.AsString;
Buf.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
Count:Integer;
begin
with TButton(Sender) do
begin
Enabled:=false;
Memo1.Text:=CNM(SpinEdit1.Value,SpinEdit2.Value,Count);
Form1.Caption:=IntToStr(Count);
Enabled:=true;
SetFocus;
end;
end;
问题二:和问题一的条件差不多,只有一处变更,《组合数字不分顺序》改为《组合数字分顺序》
 
其实你的链接说的很清楚了:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=968511
你需要变通一下,比如将元素放到一个TStringList中(SL),然后求坐标1到SL.Count的组合:
SL:=Tstringlist.Create;
for i:=48 to 57 do SL.Add(char(i));
for i:=65 to 90 do SL.Add(char(i));
for i:=97 to 122 do SL.Add(char(i));
 
最后根据坐标就知道你的组合的元素了
 
那个连接是我复制之时一起复制过来的,我也是第一次看到那帖子.但是我的问题还是没有解决呀?详细一点可以吗?
 
以下是20以内的代码,你可以将数组改为100,也可以重定义,也可以将变量m,n作为参数,注意n>=m:
procedure TForm1.SetIt();
var
a:array[1..20]of integer;
i,j,t,r,k,n,m,step:integer;
begin
n:=10;
m:=3;
t:=1;step:=0;
for j:=1 to m do begin
a[j]:=0;
while t>0 do begin
a[t]:=a[t]+1;
if a[t]>n then t:=t-1
else begin
r:=0;
for i:=1 to t-1 do
if a[t]=a then r:=100;
if r<>100 then begin
if t=m then begin
step:=step+1;
for k:=1 to t do begin
if k=1 then SL.Add('');
SL[SL.Count-1]:=SL[SL.Count-1]+' '+inttostr(a[k]);
end;
end;
if t<m then begin
//t:=t+1;a[t]:=0; {将a[t]:=0改为a[t]:=a[t-1],则为组合}
t:=t+1;a[t]:=a[t-1];
end;
end;
end;
end;
end;
end;
调用方式为:
procedure TForm1.Button1Click(Sender: TObject);
begin
if SL<>nil then FreeAndNil(SL);
SL:=TStringList.Create;
SetIt;
memo1.Text:=SL.CommaText;
end;
获得结果之后,你将相应位置的字符串替换,比如:
原来的顺序为:A,B,C,D,E,F工5个,取任意三个,那么n=5,m=3,获得SL元素结果和真实结果为:
1 2 3:A B C
1 2 4:A B D
1 2 5:A B F
1 3 4:A C D
1 3 5:A C F
1 4 5:A D F
2 3 4:B C D
2 3 5:B C F
2 4 5:B D F
3 4 5:C D E
你自己完成剩下的工作吧
 
谁知道creation_zy 的例子当中,这些语句是什么意思的?
Buf.WriteBuf(@mstr[1],Length(mstr));
Buf.ContentSize/(1024*1024)]);
 
怀念creation_zy大侠
 
后退
顶部