Solved

Letter Combination Help

Posted on 2006-11-08
17
418 Views
Last Modified: 2010-04-05
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?
0
Comment
Question by:Grant Fullen
  • 11
  • 6
17 Comments
 
LVL 17

Expert Comment

by:TheRealLoki
ID: 17902869
0
 

Author Comment

by:Grant Fullen
ID: 17902928
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
 

Author Comment

by:Grant Fullen
ID: 17903296
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
 
LVL 17

Accepted Solution

by:
TheRealLoki earned 50 total points
ID: 17904019
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
 

Author Comment

by:Grant Fullen
ID: 17910321
It works perfect.  Just the way I wanted it to.

Simple code to understand and go with it.  Great job TheRealLoki.
0
 

Author Comment

by:Grant Fullen
ID: 17910353
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
 

Author Comment

by:Grant Fullen
ID: 17910377
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
 
LVL 17

Expert Comment

by:TheRealLoki
ID: 17910922
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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:Grant Fullen
ID: 17910929
Alright.

Thanks for the help.

I can always increase the points if you'd like to show more code and stuff.
0
 

Author Comment

by:Grant Fullen
ID: 17910932
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
 

Author Comment

by:Grant Fullen
ID: 17910996
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
 
LVL 17

Expert Comment

by:TheRealLoki
ID: 17911478
Is this for a brute force routine?
0
 

Author Comment

by:Grant Fullen
ID: 17911565
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
 
LVL 17

Expert Comment

by:TheRealLoki
ID: 17926815
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
 

Author Comment

by:Grant Fullen
ID: 17926985
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
 
LVL 17

Expert Comment

by:TheRealLoki
ID: 17927286
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
 

Author Comment

by:Grant Fullen
ID: 17943904
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

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
This video discusses moving either the default database or any database to a new volume.
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now