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)ouble;
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;
StartTimeWord;
TotalCountouble;
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;
问题二:和问题一的条件差不多,只有一处变更,《组合数字不分顺序》改为《组合数字分顺序》
问题分两部份
问题一:求从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)ouble;
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;
StartTimeWord;
TotalCountouble;
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;
问题二:和问题一的条件差不多,只有一处变更,《组合数字不分顺序》改为《组合数字分顺序》