Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

Letter Combination Help

Posted on 2006-11-08
Medium Priority
564 Views
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
Question by:Grant Fullen
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 11
• 6

LVL 17

Expert Comment

ID: 17902869
0

Author Comment

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

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

TheRealLoki earned 200 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
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
end;
end;
end;

end.
0

Author Comment

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

ID: 17910353

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

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

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

Author Comment

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

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

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

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

Author Comment

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

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
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

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

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

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

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â€¦
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small printâ€¦
In this brief tutorial Pawel from AdRem Software explains how you can quickly find out which services are running on your network, or what are the IP addresses of servers responsible for each service. Software used is freeware NetCrunch Tools (httpsâ€¦
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: â€¦
Suggested Courses
Course of the Month4 days, 10 hours left to enroll