Delphi Pages Forums  

Go Back   Delphi Pages Forums > Delphi Forum > General

Lost Password?

Reply
 
Thread Tools Display Modes
  #1  
Old 02-18-2009, 06:33 PM
Ouiji Ouiji is offline
Senior Member
 
Join Date: Nov 2001
Location: US of A
Posts: 492
Default Getting possible combination's / permutations?

I have been trying to find a way to calculate the number of possible combination's in a string of a certain length, with a list of possible characters. IE: A string that is 4 characters long, and has 26 possible character variations has 456,976 possible character combination's. The first code snippet I found does work to determine that number, but it takes forever because it has to actually go through all of them. The second looks very promising.. but does not work for some reason. Does anyone have a better way of doing this?

First Code Snippet:

[DELPHI]
procedure GetWordPart(CharList: string; WordLength: Integer;
var StringList: TStringList; Str: string);
var
I: Integer;
S: string;
begin
for I := 1 to Length(CharList) do begin
S := CharList[I];
if WordLength > 1 then
GetWordPart(CharList,WordLength-1,StringList,Str+S)
else
StringList.Add(Str+S);
end;

end;

function GetAllPossibleWords(CharList: string; WordLength: Integer):integer;
var
SL: TStringList;
I,J: Integer;
S: string;
begin
SL := TStringList.Create;
GetWordPart(CharList, WordLength, SL, '');
//form1.listbox1.items := SL;
Result := SL.count;
SL.Free;
end;

[/DELPHI]

Second Code Snippet [does not work correctly]

[DELPHI]
function PossiblePermutations(TargetLength: byte): extended;

function Factorial(I: WORD): extended;
begin
result := I;
while I > 1 do begin
Dec(I);
result := result *I;
end;
end;

var
z : integer;
n, nk : extended;
begin
{

n!
n_P_k = --------
(n - k)!

}

z := Length('abcdefghijklmnopqrstuvwxyz0123456789');

n := Factorial(z);
nk := Factorial(z -TargetLength);

result := n /nk;
end;

[/DELPHI]

[Link=http://www.ouiji.net/DelphiPages/] [/Link]
[q]"not quite smart enough to be dumb"[/q]
Reply With Quote
  #2  
Old 02-19-2009, 12:19 AM
Norrit Norrit is offline
Moderator
 
Join Date: Aug 2001
Location: Landgraaf
Posts: 7,333
Default RE: Getting possible combination's / permutations?

The TStrings is slow, but can easily be removed from the first:

Code:
    procedure GetWordPart(CharList: string; WordLength: Integer;
      var Count: Integer; Str: string);
    var
      I: Integer;
      S: string;
    begin
      for I := 1 to Length(CharList) do begin
        S := CharList[I];
        if WordLength > 1 then
          GetWordPart(CharList,WordLength-1,Count,Str+S)
        else
          Inc(Count);
      end;

    end;

    function GetAllPossibleWords(CharList: string; WordLength: Integer):integer;
    var
      I,J: Integer;
      S: string;
      Count: Integer;
    begin
      GetWordPart(CharList, WordLength, count, '');
      Result := count;
    end;
This already gives you a performance boost... You could make it higher by looking at the recursive procedure...

Why the other function isn't working I don't know... I have no time to dive into this right now (although it's an interesting problem)... Perhaps tonight ;')

Objective reality is a delirium caused by lack of alcohol in blood.
There is no place like 127.0.0.1
Reply With Quote
  #3  
Old 02-19-2009, 04:51 AM
chris_w chris_w is offline
Senior Member
 
Join Date: Jan 2004
Posts: 1,397
Default RE: Getting possible combination's / permutations?

[pre]
The function worked correctly for calculating the number of
perms without repetition, your answer is correct if you
allow repitition.

Function adapted for repitition:

[/pre][DELPHI]
function PossiblePermutations(SetLength, TargetLength: byte;
RepetitionAllowed: boolean = FALSE): extended;

function Factorial(I: WORD): extended;
begin
result := I;
while I > 1 do begin
Dec(I);
result := result *I;
end;
end;

var
z : integer;
n, nk : extended;
begin
(*

Repetition not allowed

n!
n_P_k = --------
(n - k)!


Repetition allowed

n^r
*)

z := SetLength;

if RepetitionAllowed then begin
result := z;
while TargetLength > 1 do begin
result := result *z;
Dec(TargetLength);
end;
end else begin
n := Factorial(z);
nk := Factorial(z -TargetLength);

if nk < 1 then
result := n
else
result := n /nk;
end;
end;



[/DELPHI][pre]
"There is a theory which states that if ever anybody discovers
exactly what the Universe is for and why it is here, it will
instantly disappear and be replaced by something even more
bizarre and inexplicable. There is another theory which states
that this has already happened."
-- Douglas Adams
[/pre]

Chris
Reply With Quote
  #4  
Old 02-19-2009, 05:20 AM
TheBlackArrow TheBlackArrow is offline
Senior Member
 
Join Date: Sep 2007
Posts: 111
Default RE: Getting possible combination's / permutations?

Does this work for you?
[delphi]
function TForm1.PossibleCombos(Chars: String): Integer;
var
Cnt: Integer;
Perms: Int64;
begin
Cnt := Length(Chars);
Perms := 1;
while Cnt > 0 do begin
Perms := Perms * Cnt;
Cnt := Cnt - 1;
end;
Result := Perms;
end;[/delphi]

Please Accept as Answer if this helped you.

Regards,
TheBlackArrow
Reply With Quote
  #5  
Old 02-19-2009, 06:31 AM
develyoy develyoy is offline
Senior Member
 
Join Date: Nov 2007
Posts: 628
Default RE: Getting possible combination's / permutations?

[DELPHI]
uses Math;
function GetAllPossibleWords(CharList: string; WordLength: Integer):integer;
begin
Result:=Round(Power(Length(CharList),WordLength));
end;[/DELPHI]
Reply With Quote
  #6  
Old 02-19-2009, 06:32 AM
develyoy develyoy is offline
Senior Member
 
Join Date: Nov 2007
Posts: 628
Default RE: Getting possible combination's / permutations?

If you're expecting values of more than 2 billion (2^31 = 2147483648) you should switch integer to int64 or Extended
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is On

Forum Jump


All times are GMT. The time now is 01:30 AM.


Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2019, vBulletin Solutions, Inc.