微软的考试题！有胆量的进来；）

Question

我不是很明白你函数实现的功能。
你是不是是想arrange('123')的结果是这三个数的所有组合：
123，132，213，231，312，321呢？如果是的话那就简单了。

Answer 1

问题确实是微软面试题，也就是arrange('123')的结果是这三个数的所有组合：
123，132，213，231，312，321；说用冒泡法的朋友搞清楚冒泡是排序还是排列先吧；另外，你别用数组比较给我写个组合算法出来看看老师的作业容易否，就是121-->121，112，211;

Answer 2

你看好了，我现做的：unit Unit1;interfaceuses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;type
  TLink = ^Node;
  Node = record
    Str: string;
    Next: TLink;
  end;  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;var
  Form1: TForm1;
  TheLink: TLink;implementation{$R *.DFM}procedure InsertChar(var Link: TLink; Ch: Char);
var
  P, Q, TmpLink: TLink;
  TmpStr: string;
  TmpStrLen, TmpI: Integer;
begin
  if Link.Next = nil then
  begin
    New(P);
    P.Str := string(ch);
    P.Next := nil;
    Link.Next := P;
    Exit;
  end;  P := Link;
  Q := P;
  while Q.Next <> nil do
  begin
    P := Q.Next;
    TmpStr := P.Str;
    TmpStrLen := Length(TmpStr);
    for TmpI:= 0 to TmpStrLen do
    begin
      New(TmpLink);
      TmpLink.Str := Copy(TmpStr, 1, TmpI) + Ch + Copy(TmpStr, TmpI + 1, TmpStrLen - TmpI);
      TmpLink.Next := P;
      Q.Next := TmpLink;
      Q := Q.Next;
    end;
    if P.Next <> nil then
      begin
        Q.Next := P.Next;
        Dispose(P);
        P := Q;
      end
    else
      begin
        Dispose(P);
        Q.Next := nil;
      end;
  end;
end;procedure CheckSame(var Link: TLink);
var
  P, Q, TmpLink: TLink;
  TmpStr: string;
begin
  TmpLink := Link;
  while TmpLink.Next <> nil do
  begin
    TmpLink := TmpLink.Next;
    TmpStr := TmpLink.Str;
    P := TmpLink;
    while P.Next <> nil do
    begin
      Q := P;
      P := Q.Next;
      if P.Str = TmpStr then
      begin
        Q.Next := P.Next;
        Dispose(P);
        P := Q;
      end;
    end;
  end;
end;procedure CreateList(var TmpStrList: TStringList; Link: TLink);
var
  TmpLink: TLink;
begin
  TmpLink := Link;
  while TmpLink.Next <> nil do
  begin
    TmpLink := TmpLink.Next;
    TmpStrList.Add(TmpLink.Str);
  end;
end;function ProcessString(TheString: string): TStringList;
var
  TmpStrList: TStringList;
  TmpI, Len: Integer;
begin
  TmpStrList := TStringList.Create;
  New(TheLink);
  Len := Length(TheString);
  for TmpI:= 1 to Len do
  begin
    InsertChar(TheLink, TheString[TmpI]);
    CheckSame(TheLink);
  end;
  CreateList(TmpStrList, TheLink);
  Result := TmpStrList;
end;procedure TForm1.Button1Click(Sender: TObject);
var
  MyList: TStringList;
  TmpI: Integer;
begin
  MyList := ProcessString('1111');
  for TmpI:=0 to MyList.Count-1 do
    ShowMessage(MyList.Strings[TmpI]);
end;end.

Answer 3

上面的还有点小问题，改进一下：
var
  Form1: TForm1;implementation{$R *.DFM}procedure InsertChar(var Link: TLink; Ch: Char);
var
  P, Q, TmpLink: TLink;
  TmpStr: string;
  TmpStrLen, TmpI: Integer;
begin
  if Link.Next = nil then
  begin
    New(P);
    P.Str := string(ch);
    P.Next := nil;
    Link.Next := P;
    Exit;
  end;  P := Link;
  Q := P;
  while Q.Next <> nil do
  begin
    P := Q.Next;
    TmpStr := P.Str;
    TmpStrLen := Length(TmpStr);
    for TmpI:= 0 to TmpStrLen do
    begin
      New(TmpLink);
      TmpLink.Str := Copy(TmpStr, 1, TmpI) + Ch + Copy(TmpStr, TmpI + 1, TmpStrLen - TmpI);
      TmpLink.Next := P;
      Q.Next := TmpLink;
      Q := Q.Next;
    end;
    if P.Next <> nil then
      begin
        Q.Next := P.Next;
        Dispose(P);
        P := Q;
      end
    else
      begin
        Dispose(P);
        Q.Next := nil;
      end;
  end;
end;procedure CheckSame(var Link: TLink);
var
  P, Q, TmpLink: TLink;
  TmpStr: string;
begin
  TmpLink := Link;
  while TmpLink.Next <> nil do
  begin
    TmpLink := TmpLink.Next;
    TmpStr := TmpLink.Str;
    P := TmpLink;
    while P.Next <> nil do
    begin
      Q := P;
      P := Q.Next;
      if P.Str = TmpStr then
      begin
        Q.Next := P.Next;
        Dispose(P);
        P := Q;
      end;
    end;
  end;
end;procedure CreateList(var TmpStrList: TStringList; Link: TLink);
var
  TmpLink: TLink;
begin
  while Link.Next <> nil do
  begin
    TmpLink := Link.Next;
    TmpStrList.Add(TmpLink.Str);
    Link.Next := TmpLink.Next;
    Dispose(TmpLink);
  end;
  Dispose(Link);
end;function ProcessString(TheString: string): TStringList;
var
  TmpStrList: TStringList;
  TheLink: TLink;
  TmpI, Len: Integer;
begin
  TmpStrList := TStringList.Create;
  New(TheLink);
  TheLink.Next := nil;
  Len := Length(TheString);
  for TmpI:= 1 to Len do
  begin
    InsertChar(TheLink, TheString[TmpI]);
    CheckSame(TheLink);
  end;
  CreateList(TmpStrList, TheLink);
  Result := TmpStrList;
end;procedure TForm1.Button1Click(Sender: TObject);
var
  MyList: TStringList;
  TmpI: Integer;
begin
  MyList := ProcessString('1234');
  for TmpI:=0 to MyList.Count-1 do
    ShowMessage(MyList.Strings[TmpI]);
end;end.

Answer 4

微软的面试题出得很不错，打印出来并不难，题目的好在于你解决问题的思路。明白了就会变得相当简单。方法如下：// 计算全排列, 删除相同的排列
procedure StringRank(A, B: String);
var
   C: Char;
   S: String;
   i, Len: Integer;
begin
   Len := Length(A);
   if Len = 0 then
      StringPrint(B)
   else for i := 1 to Len do
   begin
      C := A[i];
      S := Copy(A, 1, i - 1);
      if Pos(C, S) = 0 then
         StringRank(S + Copy(A, i + 1, Len - i), C + B);
   end;
end;调用 StringRank('12341234', '') 即可。
至于 StringPrint(S: String) 过程应该很简单就能实现。

Answer 5

把
   begin
      C := A[i];
      S := Copy(A, 1, i - 1);
      if Pos(C, S) = 0 then
         StringRank(S + Copy(A, i + 1, Len - i), C + B);
   end;
改为：
   begin
      C := A[i];
      if Pos(C, A) = i then
      begin
         S := A;
         Delete(S, i, 1)
         StringRank(S, C + B);
      end;
   end;
效率可能会好一点。