Link to home
Start Free TrialLog in
Avatar of Grant Fullen
Grant Fullen

asked on

Need to optimize letter permutation code

Good day.

I have some code that gets all the possible combinations of a given set of characters.  So far it works good, but I need it to be optimized to work as fast as possible.

I was thinking of making it multi-threaded or whatever needs to be done to optimize it.

Here's the code:

  private
    { Private declarations }
    // from AB get A,B,AA,AB,BA,BB
    procedure FindPermutationsWithDupes(fullstring: string; SL: TStrings);
    procedure FindPermutationsOfLengthWithDupes(level, desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);

----------------------------------

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]);
      Gauge1.Progress := Gauge1.Progress + 1;
      if level <= (desiredlen_ div 2) then // to repaint less (and improve performance) change "2" to 3 or 4
        Gauge1.Repaint;
    end;
  end;
end;

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

  Gauge1.MaxValue := Trunc(maxs);
  lProgress.Caption := IntToStr(Gauge1.MaxValue);
  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;
SOLUTION
Avatar of Mike Littlewood
Mike Littlewood
Flag of United Kingdom of Great Britain and Northern Ireland image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of Grant Fullen
Grant Fullen

ASKER

Alright.

Seems to work pretty good.  But does anyone have any faster methods to add?  Just so you all know I'll be using about 65-70 characters to generate the permutations.  That's why I need it optimized.

I also want to be able to Save/Resume this list it generates.  For example, if it's 1/3 into generating the list of permutations, and I want to stop it, then I want to save what it has so far, then be able to come back and resume from where it last stopped.

You can make it write to the disk as it goes if you want if that makes it easier.
Hi again,

Ive had another look at what you are doing and I cant really suggest too much more.
It looks like you are using recursion correctly.
Oh ya, there's one major problem I forgot to add.

I mentioned in the above post that I want to do at most 70 characters.

Right now it only lets me do up to 9.  This has to be fixed so I can use 70 characters max.
Okay.  Thanks for pointing that out.  Someone told me I should use variables first then load the input to the memo but I wasn't too sure.

Maybe you can read my above post, about the main 2 issues.
Ill have a think later today as Im a little busy. Maybe someone else will come up with some other pointers for you in the mean time  :o)
Are you sure you want to find/save all permutations? They'll be a lot of them for 70 letters! :-)

I'd suggest the following:
1) A function that returns the number of permutations from a given string, e.g.
NumberOfPermutations('AB') = 6
2) A function that calculates IN CONSTANT TIME the Nth permutation, e.g.
NthPermutation('AB', 3) = 'AA'

This way you save a lot of RAM, disk and CPU time. And I suppose NthPermutation will be faster than disk loading...
Yes, I know it's a lot of combinations, and I'm sure I want to save/resume it.

Do you have any example code alkisg?
I don't have any example code,  but I think there are algorithms that let you map from counter #xxxx to permutation #xxxx.

What I meant was:
Suppose your problem is to find all decimal numbers from 1 to 10.000. Of course, your don't have to save them into an array or file. One just makes a function that converts from the internal binary representation to decimal, and if he/she needs the #1024 number, he/she just converts 1000000000b to decimal in O[1]...

So, whenever you would need permutation #xxxx in your program, you'd just use the function, and avoid storing data.
Well then do you know an algorithm that does that fast?

I still want to save it.
If you want to save all permutations, repetitive algorithms (like the one you're using) are faster that the nth-permutation ones, that's why I was asking (to avoid the trouble of searching the net).
Repetitive algorithms:
http://www.cut-the-knot.org/do_you_know/AllPerm.shtml
You may also read the papers that this pages refers to.

For nth-permutation algorithms, google for
nth-permutation
but it is NOT faster for the task you want it for...
I've already read that site, and I STILL need to know if anyone has any example code to save and resume this.

Here's a link to my other question.  Go over it.  You'll fully understand what I'm wanting.

https://www.experts-exchange.com/questions/22054086/Letter-Combination-Help.html
You want to save 66^66 numbers???!!!????
Have you calculated this? It is 1,229984803535237425357460579825e+120
This is ~1,0e+108 Terrabytes!!! You'd need more hard disk space than the whole world has to offer! :-)
...and, even if you had some million years to spend calculating all these combinations, just the act of saving them would take some more million years!!!
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
P.S. This code does not calculate smaller strings, e.g.
'A' and 'AB'
but only full-length strings, like 'ABCD'.

If you also want the smaller strings, you'll have to make another for loop to call it again with desiredLength := 1 to 4:

for desiredLength := 1 to 4 do
begin
  numComb := NumberOfCombinations(Alphabet, desiredLength);
  for i := 0 to numComb do
  begin
    s := NthCombination(Alphabet, desiredLength, i);
    //writeln(s)...
  end;
end;

and, to stop/resume you'll need to save both desiredLength and i.
Avatar of TheRealLoki
hmmm.... I was working away on another method (which urns out to be similar to the nth discussion above) I was so proud of myself for working it otu too :-(
anyway... I can get up to 13 length strings working before the Int64 limit is blown
Can anyone think of a way around this limit ?
Glad to see you still here TheRealLoki.

Thanks for the code alkisg, I'll try it tomorrow.  Please do keep working with your's TheRealLoki.  I want to try them both.
> anyway... I can get up to 13 length strings working before the Int64 limit is blown
> Can anyone think of a way around this limit ?

A big number library can be used, such as the gnu multipresision library:
http://www.swox.com/gmp/
If you just want to pick one random permutation of the letters, then you don't really need to save the entire list to disk. you could just use random( maxperutations) and use the algorithm above.
no need to store teh entire list etc...
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Sorry about the absence.

I haven't been able to test this project since now.  I pretty much have what I need now.  Points will be split.