The program loads a list of 60,000 words from a text file. The user
enters a word into an edit box and clicks the search button, the program
then searches the list and finds all words that can be created from any
combination of letters in the users entry by doing a binary search.

Presently, I am trying to code the load-list part of the program. I have
2 questions:

1. Should I load the list into a static array? If so, how do I do that?
2. I am trying to set a counter that will display the progress in the
statusbar of how many words are loading from the list. How is that done?

Please be gentle, I looked for a FAQ for this group but I couldn't find
one. So if I'm out of line with anything, let me know. Thanks. :)

Here is what I've done so far:

procedure TForm1.muLo{*word*60}Click(Sender: TObject);
var
 F: TextFile;
 Words: string;
 Count: integer;

 begin
  assignfile(F,'G:\1535 Delphi Programs\Assignment 3\Assignment3
\english.txt');
  Reset(F);
  While (not eof(F)) do
  begin
    Readln(F,Words);
    inc(Count);
  end;
 end;

    Label1.Caption := IntToStr(Count);
    Label1.Refresh;

Hope this helps.

dick

You could use a TStringList instead of an array, and then it is easy
to read in the strings using the LoadFromFile method of the list. Have
you covered lists on your course? Or any other data structures you
could use? Should you be using some kind of tree to help with the
searching you want to do later? Or do you definitely have to use a
binary chop?

    StatusBar1.Panels[0].Text := IntToStr(Count);
    if Count mod 100 = 0 then       // Leave this line out if you like
      Application.ProcessMessages;

Hint: what is the initial value of count?

--
Duncan

I'd use a ListBox or another TStrings type.
That way you can iterate through the permutations of the EditBox.Text. ie.
for i:=0 to WordList.Count-1 do // where WordList is a StringList holding
your permutations
    Memo1.Lines.Add(ListBox1.Items.IndexOfName(WordList.Strings[i]));
This will place each word in a Memo.

The hard part for me would be the making of the permutations of the word
entered in the EditBox
Good luck

I'll work on it, and may be back with more queries.

--
? John Stockton, Surrey, UK.  j...@merlyn.demon.co.uk   D3  Turnpike v4  MIME. ?
  <URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
  <URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ;
  <URL:http://www.borland.com/newsgroups/guide.html> news:borland.* Guidelines

One approach is to generate all permutations of the subject string and
use IndexOf to search, having set SL.Sorted := true beforehand.

Knuth (The Art of Computer Programming) discusses generating
permutations in detail as do other texts on algorithms.  Doing this well
is a bit complicated.

Another approach, a simple method, is to find a candidate in the string
list - call it W - and check that all characters in the subject S occur
in W:

        function Check(S, W: string): Boolean;
        var I, P: integer;
        begin
          Result := Length(S) = length(W); I := 1;
          while Result and I <= length(S) do begin
            P := Pos(S[I], W);
            Result := P <> 0;
            if Result then begin
              W[P] := ' ' {to handle repetitions}; Inc(I)
            end
          end
        end;

...after forcing S and W to the same case if necessary and using Trim to
clip off white space.

Of course a linear search finds all candidates, but it requires looking
at 60,000 of them.  To improve on that, sort the word list by length
beforehand with a utility, if possible, but a CustomSort can be written
for TStringlist to do this.  Then a binary search on length ought to be
faster.

I have tried the code, but I'm getting the following error message when
I try to compile: "operator not applicable to this operand type". I'm
not sure if I'm setting this thing up properly. I'll comment the line
which gives the error message with ERROR.

unit MainWindow;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,
Forms,
  Dialogs, Menus, StdCtrls, ExtCtrls, Mask, ComCtrls;

type
  TForm1 = class(TForm)
    MainMenu1: TMainMenu;
    muFile: TMenuItem;
    muLo{*word*60}: TMenuItem;
    Search1: TMenuItem;
    muSearch: TMenuItem;
    muSave: TMenuItem;
    N1: TMenuItem;
    muExit: TMenuItem;
    Help1: TMenuItem;
    muAbout: TMenuItem;
    sbStatusBar: TStatusBar;
    ListBox1: TListBox;
    Panel1: TPanel;
    edSearchBox: TEdit;
    dbOpenFile: TOpenDialog;
    procedure muAboutClick(Sender: TObject);
    procedure muLo{*word*60}Click(Sender: TObject);
    procedure muSearchClick(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  DictText: TextFile;
  index: integer;
  IsDictLoaded : boolean = false;
  I, P: integer;

  DictArray: Array[1..100000] of string;

implementation

uses AboutWindow;

{$R *.dfm}

procedure TForm1.muAboutClick(Sender: TObject);
begin
  fmAboutWindow.ShowModal
end;

procedure TForm1.muLo{*word*60}Click(Sender: TObject);

 begin
    index := 1;
    if dbOpenFile.Execute then // If the open dialog box is executed
    AssignFile(DictText,dbOpenFile.FileName);
    Reset(DictText);

  While (not eof(DictText)) do
    begin

      Readln(DictText,DictArray[index]);
      if (index mod 10) = 0 Then
      sbStatusBar.Panels[0].Text :='Dictionary Size:' +  IntToStr
(index);
      application.ProcessMessages;
      inc(index);
    end;
    CloseFile(DictText);
    IsDictLoaded := true;
  end;

procedure TForm1.muSearchClick(Sender: TObject);

function Check(SrchWrd, DictArray: string): Boolean;

    begin
      SrchWrd := edSearchBox.Text;
      Result := Length(SrchWrd) = length(DictArray); I := 1;
      while Result and I <= length(SrchWrd) do // ERROR
      begin
        P := Pos(SrchWrd[I], DictArray);
        Result := P <> 0;
        if Result then begin
          DictArray[P] := ' ' {to handle repetitions}; Inc(I)
      end
    end
  end;

begin
Application.MessageBox(' Dictionary is not loaded, please try again'
                        , 'ERROR!!');
end;

end.

  Result and I

... is logical and integer, and {*word*88}s.

  Result and (I <= length(SrchWrd))

... is logical and logical, and is OK

Alan Lloyd
alangll...@aol.com

Thank you Mr.LLoyd, that did the trick.

But I'm having problems implementing this function. I don't think I
totally understand how to call it, or how works. I've commented the
function with some guesses and questions.

Basically, if I call the function from my procedure
TForm1.edSearchBoxChange(Sender: TObject); procedure, how can I make use
of its return value if it returns boolean? What I need to do is have a
way to return all permutations of the typed-in word that exist in the
list and display them in the listbox.

Am I even close to being on the right track with what I have so far? :

unit MainWindow;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls,
Forms,
  Dialogs, Menus, StdCtrls, ExtCtrls, Mask, ComCtrls;

type
  TForm1 = class(TForm)
    MainMenu1: TMainMenu;
    muFile: TMenuItem;
    muLo{*word*60}: TMenuItem;
    Search1: TMenuItem;
    muSearch: TMenuItem;
    muSave: TMenuItem;
    N1: TMenuItem;
    muExit: TMenuItem;
    Help1: TMenuItem;
    muAbout: TMenuItem;
    sbStatusBar: TStatusBar;
    Panel1: TPanel;
    edSearchBox: TEdit;
    dbOpenFile: TOpenDialog;
    lbFoundList: TListBox;
    procedure muAboutClick(Sender: TObject);
    procedure muLo{*word*60}Click(Sender: TObject);
    procedure muSearchClick(Sender: TObject);
    procedure edSearchBoxChange(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;
  DictText: TextFile;
  index: integer;
  IsDictLoaded : boolean = false;
  I, P: integer;

  DictArray: Array[1..100000] of string;

implementation

uses AboutWindow;

{$R *.dfm}

procedure TForm1.muAboutClick(Sender: TObject);
begin
  fmAboutWindow.ShowModal
end;

procedure TForm1.muLo{*word*60}Click(Sender: TObject);

  begin
    index := 1;
    if dbOpenFile.Execute then // If the open dialog box is executed
    AssignFile(DictText,dbOpenFile.FileName);
    Reset(DictText);

  While (not eof(DictText)) do
    begin

      Readln(DictText,DictArray[index]);
      if (index mod 10) = 0 Then
      sbStatusBar.Panels[0].Text :='Dictionary Size:' +  IntToStr
(index);
      application.ProcessMessages;
      inc(index);
    end;
      CloseFile(DictText);
      IsDictLoaded := true;
  end;

procedure TForm1.muSearchClick(Sender: TObject);

  begin
     if (not IsDictLoaded) then
     Application.MessageBox(' Dictionary is not loaded! Please try
again.'
                            , 'ERROR!!')

  end;

  function Check(SrchWrd, ListWord: string): Boolean;
    begin
      // Result is true if list word is equal to typed word
      Result := Length(SrchWrd) = length(ListWord); I := 1;

      // Doesn't this eliminate any words not of equal length?
      // What does I <= length(SrchWrd) do
      while Result and (I <= length(SrchWrd)) do
      begin

      // Does this compare the first character of both words?
        P := Pos(SrchWrd[I], ListWord);
      // Does this say that the character cannot be in the 0 position of
the string
      // I'm confused
        Result := P <> 0;

      // If not the 0th character change the P'th character to a blank
      // character so that it won't be read again...
      // Inc(I) = go to the next character
        if Result then begin
          ListWord[P] := ' ' {to handle repetitions}; Inc(I)
      end;
    end;

   end;

procedure TForm1.edSearchBoxChange(Sender: TObject);
 var
   TypedWord, DictWord : string;
   i : integer;

  begin
    i := 1;
    TypedWord := edSearchBox.Text;

    while (i <= index ) do
    begin
    DictWord := DictArray[i];
    check(TypedWord, DictWord);
    lbFoundList.Items.Add(DictArray[i]);

    inc(i);
    end;

  end;
end.

Comparing sets are quick, but a set has a single entry for any number of each
character.So I do a (quick) set compare, only if this passes do I do a
character count compare.

 So going through the file I make a set of the read characters and compare it
to a set from the base characters. Only if they are the same do I do a
character count compare.

To do the character count compare I have two array[0..255] of char, and put the
count of characters in the Ord(char) element. I do this for the base
string.Then after filling the second array from the read string, I do a memory
compare of the arrays. If they are identical then the strings are permutations
of each other. I also do an initial test to see if the strings are identical
rather than a permutation.

I use a stream in the procedure, you have to create a stream, load it with a
file, and pass it to the procedure.

type
  TCharSet = set of char;  // holds a set of the characters in a string
  TCharArray = array[0..255] of integer; // holds count of number of each char
in strings

function MakeCharSet(Str : string) : TCharSet;
var
  i : integer;
begin
  Result := [];
  for i := 1 to Length(Str) do
    Include(Result, Str[i]);
end;

function StringI{*word*237}(CompStr, PermStr : string; CompCharArray : TCharArray) :
boolean;
var
  PermCharArray : TCharArray;
  i : integer;
begin
  if PermStr = CompStr then
    Result := false; // same string, not a permutation
  FillChar(PermCharArray, SizeOf(TCharArray), #0);
  for i := 1 to Length(PermStr) do
    inc(PermCharArray[Ord(PermStr[i])]);
  Result := CompareMem(@CompCharArray, @PermCharArray, SizeOf(TCharArray));
end;

procedure TForm1.ListPermutation(CompStr : string; Stream : TStream; SL :
TStringList);
var
  CompStrLen, i : integer;
  CompCharArray : TCharArray;
  CompCharSet, PermCharSet : TCharSet;
  PermStr : string;
begin
  {make a set of the comparison string}
  CompCharSet := MakeCharSet(CompStr);
  CompStrLen := Length(CompStr);
  {clear the character array}
  FillChar(CompCharArray, SizeOf(TCharArray), #0);
  {fill the char array with the count of comparison string characters}
  for i := 1 to Length(CompStr) do
    inc(CompCharArray[Ord(CompStr[i])]);
  SL.Clear;
  {make a permutation string}
  SetLength(PermStr, CompStrLen);
  Stream.Seek(0, soFromBeginning);
  {now read all the stream incrementing every byte and reading a ComStrLen each
time}
  for i := 0 to Stream.Size - 1 do begin
    {read into permutation string}
    Stream.Read(PermStr[1], CompStrLen);
    {make a set for the characters}
    PermCharSet := MakeCharSet(PermStr);
    {now check that set of characters in strings are same (set is same),
     and that same numbers of chars are in both (char array is same) ...}
    if (PermCharSet = CompCharSet) and StringI{*word*237}(PermStr, CompCharArray)
then
      {... if so add it to list}
      SL.Add(PermStr);
  end;
end;

One could do an improvement (a la Boyer-Morse-Horspool) by checking if the
CompareStr set is empty. If it is then there is no possible permutation for the
compare str len. So jump on the length of the compare string before reading the
stream again.

Also one could check that the permutation is not already in the list before
adding it (SL.IndexOf(CompareStr) = -1) == not in list.

One advantage of the above technique is that you don't have to construct
permutations of the base string characters. You just check if they are the same
characters but not the same string.

I know Eureka is a newbie, but there some not very difficult concepts in the
above code which are useful to learn - Sets, Arrays, Streams. With regard to
the latter I have a small help file on streams which I wrote after I attacked
what I thought was the very difficult subject of streams - and found they were
simple after all.

Alan Lloyd
alangll...@aol.com

"If it is, then there is no possible permutation of the characters in the base
string in the next compare-str-len characters. So jump on the length ..."

Alan Lloyd
alangll...@aol.com