发新话题
打印

关于排列组合的一个算法的探讨

关于排列组合的一个算法的探讨

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

TOP

发新话题