Letter Combination Help

I play this game Text Twist.  It gives you 6 letters that you have to make words out of.

I'm wanting to make a program that will give every possible combination of those 6 letters.

So 6 to the 6th power is 279,936.  That's how many combinations it should produce.

Any ideas?
Grant FullenAsked:
Who is Participating?
 
TheRealLokiConnect With a Mentor Senior DeveloperCommented:
yes, I understand the concept
here's a demo I wrote for you to demonstrate the 2 methods of permuations
firsty, your request, and secondly, without reusing the letters

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
// from AB get A,B,AA,AB,BA,BB
    procedure FindPermutationsWithDupes(fullstring: string; SL: TStrings);
    procedure FindPermatationsOfLengthWithDupes(level, desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);
// from AB get A,B,AB,BA
    procedure FindPermutations(fullstring: string; SL: TStrings);
    procedure FindPermatationsOfLength(level, desiredlen_: integer; fullstring, usedstring_, stringsofar: string; SL: TStrings);
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
begin
   FindPermutationsWithDupes(Edit1.text, memo1.Lines);
//   FindPermutations(Edit1.text, memo1.Lines);
end;

procedure TForm1.FindPermutationsWithDupes(fullstring: string; SL: TStrings);
var
  desiredlen: integer;
begin
  SL.BeginUpdate;
  try
    SL.Clear;
    for desiredlen := 1 to length(fullstring) do
      FindPermatationsOfLengthWithDupes(1, desiredlen, fullstring, '', SL);
  finally
    SL.EndUpdate;
  end;
end;

procedure TForm1.FindPermatationsOfLengthWithDupes(level, desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);
var
  j: integer;
begin
  for j := 1 to length(fullstring) do
  begin
    if level < desiredlen_ then
      FindPermatationsOfLengthWithDupes(level + 1, desiredlen_, fullstring, stringsofar + fullstring[j], SL)
    else
      Sl.Add(stringsofar + fullstring[j]);
  end;
end;

procedure TForm1.FindPermutations(fullstring: string; SL: TStrings);
var
  desiredlen: integer;
  i: integer;
  usedstring: string;
begin
  SL.BeginUpdate;
  try
    SL.Clear;
    for desiredlen := 1 to length(fullstring) do
    begin
      usedstring := '';
      for i := 1 to length(fullstring) do usedstring := usedstring + 'N';
      FindPermatationsOfLength(1, desiredlen, fullstring, usedstring, '', SL);
    end;
  finally
    SL.EndUpdate;
  end;
end;

procedure TForm1.FindPermatationsOfLength(level, desiredlen_: integer; fullstring, usedstring_, stringsofar: string; SL: TStrings);
var
  j: integer;
  tempstring: string;
begin
  for j := 1 to length(fullstring) do
  begin
    if usedstring_[j] = 'N' then
    begin
      tempstring := usedstring_;
      tempstring[j] := 'Y';
      if level < desiredlen_ then
        FindPermatationsOfLength(level + 1, desiredlen_, fullstring, tempstring, stringsofar + fullstring[j], SL)
      else
        Sl.Add(stringsofar + fullstring[j]);
    end;
  end;
end;

end.
0
 
TheRealLokiSenior DeveloperCommented:
0
 
Grant FullenAuthor Commented:
The first link is close to what I want.  But I don't need to to check against a dictionary or anything else.

Here's a small scale example.  If I have the letters a, b, and c then I should be returned these:

a
b
c
aaa  bbb  ccc
aab  baa  cca
aac  bab  ccb
aba  bac  caa
abb  bba  cab
abc  bbc  cac
aca  bca  cba
acb  bcb  cbb
acc  bcc   cbc

Those are all the possible combinations of 'abc'.  I need to be able to produce something like that out of any 6 or more letters I put in.
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
Grant FullenAuthor Commented:
I forgot to add the rest of the list.

a
b
c
aaa  bbb  ccc   aa
aab  baa  cca   ab
aac  bab  ccb   ac
aba  bac  caa   ba
abb  bba  cab   bb
abc  bbc  cac    bc
aca  bca  cba    ca
acb  bcb  cbb    cb
acc  bcc   cbc    cc

I only added the pairs of letters.  But I'm sure you get the point.  I want to have every possible combination to be returned.
0
 
Grant FullenAuthor Commented:
It works perfect.  Just the way I wanted it to.

Simple code to understand and go with it.  Great job TheRealLoki.
0
 
Grant FullenAuthor Commented:
I already accepted your answer because it works the way I asked.

But there's just one thing.  It gets laggy after I put 7 letters in.  I know it's because of all the combinations.

Is there anyway to at least show a progress bar?  I've also heard about using multithreaded applications to handle bigtime calculations like that.
0
 
Grant FullenAuthor Commented:
Is there a way to use multithreads?

I know that finding the permutations without the dupes is a whole lot faster, but I need the ones with the dupes.
0
 
TheRealLokiSenior DeveloperCommented:
how many letters (max) will you need to deal with?
(this dictates how you'd write it)
You could make it threaded, or multithreaded. what you'd do is decide something like
"if there are 5 more levels to do, make a new thread for each character at this level"
and then wait for the threads to finish.
The performance would probably increase a little, but the resource use would also increase
(probably not a problem unless you're examing text with 100s or letters or more...)

If you made it single threaded, you could do a simple progress bar also, and still allow the user to do other things.
eg. synchronize(UpdateProgress)

If you use the current code, you could also do a progress bar, by a maths calculation on length and level, but only update the progress bar if on a certain level or higher (to reduce slowing things down with needless miniscule updates to the progress bar)

Up to you, but this is only a 50 pt question ;-)
0
 
Grant FullenAuthor Commented:
Alright.

Thanks for the help.

I can always increase the points if you'd like to show more code and stuff.
0
 
Grant FullenAuthor Commented:
Just let me know how many points and I can do it.

And I'll be using 66 characters, which is a serious load of combinations.  That's why I would like to be able to do it in portions, instead of all at one time.
0
 
Grant FullenAuthor Commented:
What would ultimately finish this is if I could somehow pause and save where it's at in generating the combinations, and then come back to where was and continue.

I don't know if this is possible but if it is let me know.
0
 
TheRealLokiSenior DeveloperCommented:
Is this for a brute force routine?
0
 
Grant FullenAuthor Commented:
I don't think a "brute force routine" is what I'm wanting.  I don't know what a brute force routine is, but if it could help make this work then maybe you could explain it a little bit.

See, I'm kind of making my own version of TextTwist, and I'm going to have an easy, medium, and hard setting.  Then I'm going to have an additional HangMan option.  So the sentences for the hangman could be long.  

I figured 66 characters could be the max amount of characters for the hard level of hangman sentence, since that's about 16 words.

Maybe that clears it up.
0
 
TheRealLokiSenior DeveloperCommented:
btw, 6 to the 6th power is 46,656 not 279,936 ;-)

By adding a progress bar, you will of course, slow things down a bit (depending on how often you refresh)
drop a TProgressbar on the form, and change the following procedures

uses math;

procedure TForm1.FindPermutationsWithDupes(fullstring: string; SL: TStrings);
var
  desiredlen: integer;
var
  maxs: double;
  i: integer;
begin
  maxs := 0;
  for i := length(edit1.text) downto 1 do
    maxs := maxs + power(length(fullstring), i);
{eg. for a 4 letter string, you calculate as
  power(4, 4) + power(4, 3) + power(4, 2) + power(4, 1)}

  Progressbar1.Max := Trunc(maxs);
  lProgress.Caption := IntToStr(Progressbar1.Max);
  SL.BeginUpdate;
  try
    SL.Clear;
    for desiredlen := 1 to length(fullstring) do
      FindPermutationsOfLengthWithDupes(1, desiredlen, fullstring, '', SL);
  finally
    SL.EndUpdate;
  end;
    lListcount.Caption := IntToStr(Sl.Count);
end;


procedure TForm1.FindPermutationsOfLengthWithDupes(level, desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);
var
  j: integer;
begin
  for j := 1 to length(fullstring) do
  begin
    if level < desiredlen_ then
      FindPermutationsOfLengthWithDupes(level + 1, desiredlen_, fullstring, stringsofar + fullstring[j], SL)
    else
    begin
      Sl.Add(stringsofar + fullstring[j]);
      Progressbar1.Position := Progressbar1.Position + 1;
      if level <= (desiredlen_ div 2) then // to repaint less (and improve performance) change "2" to 3 or 4
        Progressbar1.Repaint;
    end;
  end;
end;

I'll make a multithreaded version for another 250 pts :-)
Would the "pausing" and "resuming" require the list "so far" to be saved also?
0
 
Grant FullenAuthor Commented:
Alright.

The progress bar works great.

Do I need to post a new question so I can add the points?  

The pausing and resuming would work like this.  Let's say I'm 1/3 through generating the list, but I want to pause it and save whatever is generated so far.  Then I'll come back and resume adding to the list that's generated so far.
0
 
TheRealLokiSenior DeveloperCommented:
btw, for large numbers, the progress abr routine will need some twinking, since "max" is an integer
we'd set it to 0-100, and do a percentage instead for the big values

Depending on the size of the string (36 chars) and you are 1/3 through, it could still take a while to save the list to disk. Would you prefer it to write to disk as it goes? This will also make "resuming" easier, since it could just do append

Since the basic routine is done, I think you should start a new question, and put a link to this one, asking for people to create a multithreaded routine for it. eg. n threads calculating and then returning the results, with the ability to save.
Give the gurus a chance to flex their muscles
0
 
Grant FullenAuthor Commented:
Sounds good.

Yes you can make it write to disk as it goes if that'll make it easier.

There's only one problem though.  Now it only lets me use up to 9 characters.  I need 66 max.  Hopefully that's not a problem.

I'll go ahead and make the new question.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.