Алгоритм медленной анаграммы

Я работал над алгоритмом перестановки букв в слове, но поиск правильного слова занимает много времени.

var
  Form1: TForm1;
  DictionaryArray : array[0..2000] of string;

const Numbrs : string = '123456789';

implementation

{$R *.dfm}

function GenerateSequence(CPoint : String; L : Integer): String;
var
  Increaser : array[1..8] of Integer;
  i : Integer;
  AnagramSequence : String;
begin
  FillChar(Increaser, SizeOf(Increaser), 0);
  for i := 1 to Length(CPoint) do
    Increaser[9 - i] := StrToInt(CPoint[L + 1 - i]);

  //==========================================//

  if Increaser[8] <= L then
    Increaser[8] := Increaser[8] + 1;

  if Increaser[8] > L then
  begin
    Increaser[8] := 1;
    Increaser[7] := Increaser[7] + 1;
  end;

  if (Increaser[7] > L - 1) and (L > 3) then
  begin
    Increaser[8] := 1;
    Increaser[7] := 1;
    Increaser[6] := Increaser[6] + 1;
  end;

  if (Increaser[6] > L - 2) and (L > 4) then
  begin
    Increaser[8] := 1;
    Increaser[7] := 1;
    Increaser[6] := 1;
    Increaser[5] := Increaser[5] + 1;
  end;

  if (Increaser[5] > L - 3) and (L > 5) then
  begin
    Increaser[8] := 1;
    Increaser[7] := 1;
    Increaser[6] := 1;
    Increaser[5] := 1;
    Increaser[4] := Increaser[4] + 1;
  end;

  if (Increaser[4] > L - 4) and (L > 6) then
  begin
    Increaser[8] := 1;
    Increaser[7] := 1;
    Increaser[6] := 1;
    Increaser[5] := 1;
    Increaser[4] := 1;
    Increaser[3] := Increaser[3] + 1;
  end;

  if (Increaser[3] > L - 5) and (L > 7) then
  begin
    Increaser[8] := 1;
    Increaser[7] := 1;
    Increaser[6] := 1;
    Increaser[5] := 1;
    Increaser[4] := 1;
    Increaser[3] := 1;
    Increaser[2] := Increaser[2] + 1;
  end;

  //==========================================//

  AnagramSequence := IntToStr(Increaser[1]) + IntToStr(Increaser[2]) + IntToStr(Increaser[3]) + IntToStr(Increaser[4]) + IntToStr(Increaser[5]) + IntToStr(Increaser[6]) + IntToStr(Increaser[7]) + IntToStr(Increaser[8]);
  Result := AnsiReplaceStr(AnagramSequence, '0', '')
end;

procedure LoadDictionary(DictionaryPath : String);
var
  F : TextFile;
  i : Integer;
begin
  i := 0;
  AssignFile(F, DictionaryPath);
  Reset(F);
  while not Eof(F) do
  begin
    Readln(F, DictionaryArray[i]);
    Inc(i);
  end;
  CloseFile(F);
end;

function CheckInDictionary(RandedWord : String): Boolean;
begin
  if (AnsiIndexText(RandedWord, DictionaryArray) = -1) then
    Result := False
  else
    Result := True;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  LoadDictionary('wordlist.txt');
  Label1.Caption := 'Dictionary: Loaded.';
  Label1.Font.Color := clGreen;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  FRand, MRand, RandedWord, AnagramSequence : String;
  RandedIndex, i : Integer;
begin
  FRand := Edit1.Text;
  MRand := FRand;
  RandedWord := MRand;
  AnagramSequence := StringOfChar('1', Length(FRand));
  while CheckInDictionary(RandedWord) = False do
  begin
    MRand := FRand;
    RandedWord := '';

    AnagramSequence := GenerateSequence(AnagramSequence, Length(FRand));

    for i := Length(AnagramSequence) downto 1 do
    begin
      Application.ProcessMessages;
      RandedIndex := StrToInt(AnagramSequence[i]);
      RandedWord := RandedWord + MRand[RandedIndex];
      Delete(MRand, RandedIndex, 1);
    end;

  end;
  Edit2.Text := RandedWord;
end;

Как я могу улучшить этот алгоритм?


person Mahmoud K.    schedule 16.02.2010    source источник
comment
Похоже на чей-то домашний вопрос.   -  person Warren P    schedule 16.02.2010


Ответы (1)


Если вы проверяете, есть ли в словаре анаграмма приведенных букв, вы можете сделать следующее:

  1. (это можно вычислить заранее) для каждого слова в словаре отсортируйте буквы, например store (aht=hat). и отсортировать словарь по имени (TStringlist может сделать это с помощью пар имя-значение)
  2. отсортировать буквы в строке (например, hello -> ehllo)
  3. в словаре найдите элементы, имя которых совпадает с отсортированной строкой букв.
person Ritsaert Hornstra    schedule 16.02.2010
comment
Нет, повторное вычисление букв — плохая идея, когда у вас большой словарь. - person Mahmoud K.; 16.02.2010
comment
@goblin: Можете ли вы сказать мне, почему нет: расширенный словарь (дополненный отсортированными строками) будет только в два раза больше. Если вы не можете отсортировать отсортированные строки, вы всегда просматриваете значительную часть словаря; Я попытался дать алгоритм, чтобы сделать поиск быстрее. Я вижу, что словарь все еще помещается в основную память. - person Ritsaert Hornstra; 16.02.2010
comment
Гоблин, у тебя нет большого словаря. У вас есть словарь только с 2001 словом. - person Rob Kennedy; 16.02.2010