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 FindPermutationsOfLengthWi thDupes(le vel, desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);
-------------------------- --------
procedure TForm1.FindPermutationsOfL engthWithD upes(level , desiredlen_: integer; fullstring, stringsofar: string; SL: TStrings);
var
j: integer;
begin
for j := 1 to length(fullstring) do
begin
if level < desiredlen_ then
FindPermutationsOfLengthWi thDupes(le vel + 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.FindPermutationsWit hDupes(ful lstring: 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
FindPermutationsOfLengthWi thDupes(1, desiredlen, fullstring, '', SL);
finally
SL.EndUpdate;
end;
lListcount.Caption := IntToStr(Sl.Count);
end;
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(
procedure FindPermutationsOfLengthWi
--------------------------
procedure TForm1.FindPermutationsOfL
var
j: integer;
begin
for j := 1 to length(fullstring) do
begin
if level < desiredlen_ then
FindPermutationsOfLengthWi
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.FindPermutationsWit
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
FindPermutationsOfLengthWi
finally
SL.EndUpdate;
end;
lListcount.Caption := IntToStr(Sl.Count);
end;
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
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.
ASKER
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.
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.
ASKER
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.
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...
I'd suggest the following:
1) A function that returns the number of permutations from a given string, e.g.
NumberOfPermutations('AB')
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...
ASKER
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?
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.
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.
ASKER
Well then do you know an algorithm that does that fast?
I still want to save it.
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...
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...
ASKER
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
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,229984803535237425357460 579825e+12 0
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!!!
Have you calculated this? It is 1,229984803535237425357460
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
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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(Alpha bet, 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.
'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(Alpha
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.
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 ?
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 ?
ASKER
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.
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/
> 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...
no need to store teh entire list etc...
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
I haven't been able to test this project since now. I pretty much have what I need now. Points will be split.
ASKER
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.