• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 828
  • Last Modified:

Anagram creator

Has any body got any source code to work out all the permutations of a given string
eg if string = "abc" then all given permutations are
"abc,acb,cab,bac,bca,cba"
Thanks
0
eldraco
Asked:
eldraco
  • 3
  • 2
1 Solution
 
mikelittlewoodCommented:
Just to let people know how many permutations that is

a = 1
ab = 2
abc = 9
abcd = 24 i.e. 4x3x2x1
abcde = 120 i.e. 5x4x3x2x1
etc.

I am currently trying to work out how to loop correctly but not too easy  :p)
0
 
mikelittlewoodCommented:
oops I did that wrong

a = 1
ab = 2
abc = 6
abcd = 24 i.e. 4x3x2
abcde = 120 i.e. 5x4x3x2
etc.
0
 
pritaeasSoftware EngineerCommented:
{
  Uses a form with an editbox, button and listbox
  crude version, nodes are NOT freed!
}

unit frmMain;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TformMain = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    ListBox1: TListBox;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  formMain: TformMain;

implementation

{$R *.DFM}

type
  TNode = class(TObject)
  private
    FText: string;
    FRemainder: string;
    FLeaves: array of TNode;
    FList: TStringList;
    FLen: Integer;
  public
    constructor Create(const AText, ARemainder: string; AList: TStringList; ALen: Integer);
    destructor Destroy; override;
    procedure CreateLeaves;
  end;

procedure TformMain.Button1Click(Sender: TObject);
var
  startNode: TNode;
  sl: TStringList;
begin
  Listbox1.Items.Clear;
  sl := TStringList.Create;
  sl.Sorted := True;
  sl.Duplicates := dupIgnore;
  startNode := TNode.Create('', Edit1.Text, sl, Length(Edit1.Text));
  Listbox1.Items.Assign(sl);
end;

{ TNode }

constructor TNode.Create(const AText, ARemainder: string; AList: TStringList; ALen: Integer);
begin
  inherited Create;
  FText := AText;
  FRemainder := ARemainder;
  FList := AList;
  FLen := ALen;
  CreateLeaves;
end;

procedure TNode.CreateLeaves;
var
  idx, len: Integer;
begin
  if FRemainder = '' then begin
    FList.Add(FText);
    Exit;
  end;

  len := Length(FRemainder);
  SetLength(FLeaves, len);
  for idx := 1 to len do
    FLeaves[idx - 1] := TNode.Create(FText + Copy(FRemainder, idx, 1),
      Copy(FRemainder, 1, idx - 1) + Copy(FRemainder, idx + 1, len), FList, FLen);
end;

destructor TNode.Destroy;
var
  idx: Integer;
begin
  for idx := 0 to Length(FLeaves) do
    FLeaves[idx].Free;

  inherited;
end;

end.
0
 
pritaeasSoftware EngineerCommented:
Note: you could make the procedure a lot smarter, but that's only needed if you use a lot of duplicate characters in a word. I now use the sorted/duplicates properties of tstringlist to remove the unwanted entries. This could be inserted into the algorithm. Since this thing is building a tree, it could take a long while to complete for large words. You may experience stack overflows and such.

prit.
0
 
pritaeasSoftware EngineerCommented:
// This one is less memory intensive ;>

unit frmMain;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TformMain = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    ListBox1: TListBox;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  formMain: TformMain;

implementation

{$R *.DFM}

type
  TNode = class(TObject)
  private
    FText: string;
    FRemainder: string;
    FList: TStringList;
    FLen: Integer;
  public
    constructor Create(const AText, ARemainder: string; AList: TStringList; ALen: Integer);
    procedure CreateNodes;
  end;

procedure TformMain.Button1Click(Sender: TObject);
var
  startNode: TNode;
  sl: TStringList;
begin
  Listbox1.Items.Clear;
  sl := TStringList.Create;
  sl.Sorted := True;
  sl.Duplicates := dupIgnore;
  startNode := TNode.Create('', Edit1.Text, sl, Length(Edit1.Text));
  Listbox1.Items.Assign(sl);
  startNode.Free;
end;

{ TNode }

constructor TNode.Create(const AText, ARemainder: string; AList: TStringList; ALen: Integer);
begin
  inherited Create;
  FText := AText;
  FRemainder := ARemainder;
  FList := AList;
  FLen := ALen;
  CreateNodes;
end;

procedure TNode.CreateNodes;
var
  idx, len: Integer;
  node: TNode;
begin
  if FRemainder = '' then begin
    FList.Add(FText);
    Exit;
  end;

  len := Length(FRemainder);
  for idx := 1 to len do begin
    node := TNode.Create(FText + Copy(FRemainder, idx, 1),
      Copy(FRemainder, 1, idx - 1) + Copy(FRemainder, idx + 1, len), FList, FLen);
    node.Free;
  end;
end;

end.
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now