关于排列组合的一个算法的探讨
这个周末,朋友的朋友出了一个排列组合的问题,需求如下:
A:9位数
B:由1-9这九个数组成,而且不允许重复,不允许有0
C:生成到文本文件里
其实也就是全排列问题,因为只是要结果,所以没考虑算法的优化,代码执行了5个多小时。权当抛砖引玉吧,代码如下,期待大家有好的算法^-^
{****************************************************}
procedure TForm1.Button1Click(Sender: TObject);
Var
Ls, SameLs : TStringList;
I : Int64;
J : Integer;
AStr : String;
begin
Ls := TStringList.Create;
SameLs := TStringList.Create;
Try
Try
I := 123456788;
While I < 987654320 do
begin
Application.ProcessMessages;
AStr := IntToStr(I);
SameLs.Clear;
For J := 1 to 9 do
begin
if AStr[J] = '0' then Break;
if SameLs.IndexOf(AStr[J]) <> -1 then Break;
SameLs.Add(AStr[J]);
end;
if SameLs.Count = 9 then
begin
Ls.Add(AStr);
Edit1.Text := AStr;
end;
Inc(I);
end;
Ls.SaveToFile('C:9.txt');
Finally
FreeAndNil(SameLs);
end;
Finally
FreeAndNil(Ls);
end;
end;
{****************************************************}
结果那哥们说需求变了,需求如下:
A:8位数 //修改的地方
B:由1-9这九个数组成,而且不允许重复,不允许有0
C:生成到文本文件里
那么代码对应修改如下,执行时间缩小到了20多分:
{****************************************************}
procedure TForm1.Button2Click(Sender: TObject);
Var
Ls, SameLs : TStringList;
I : Int64;
J : Integer;
AStr : String;
begin
Ls := TStringList.Create;
SameLs := TStringList.Create;
Try
Try
I := 12345678;
While I < 98765433 do
begin
Application.ProcessMessages;
AStr := IntToStr(I);
SameLs.Clear;
For J := 1 to 8 do
begin
if AStr[J] = '0' then Break;
if SameLs.IndexOf(AStr[J]) <> -1 then Break;
SameLs.Add(AStr[J]);
end;
if SameLs.Count = 8 then
begin
Ls.Add(AStr);
Edit1.Text := AStr;
end;
Inc(I);
end;
Ls.SaveToFile('C:8.txt');
Finally
FreeAndNil(SameLs);
end;
Finally
FreeAndNil(Ls);
end;
end;
{****************************************************}
呵呵,想来想去我只想到这么实现了, 大家讨论讨论看还有什么好的法子吗?