关于排列组合的一个算法的探讨
这个周末，朋友的朋友出了一个排列组合的问题，需求如下：
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;
{****************************************************}
呵呵，想来想去我只想到这么实现了， 大家讨论讨论看还有什么好的法子吗？
