Formula for # of combinations?

[Stooney]

I can't seem to find an answer for this probably because I don't know the proper keywords.  Basically I'm trying to figure a formula for calculating the max number of possible number of combinations using a set number of characters, minimum length, and maximum length.

 

Example:

 

$chars=64; (a-z, A-Z, 0-9)

$min=3; (3 characters long)

$max=16; (16 character long)

 

The combinations include all of the characters, (64 would be 64 unique characters) starting with combinations 3 chars long (aaa, aab, aac, etc) and ending at combinations 16 chars long (aaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaab, etc). 

 

I don't need to actually put the string together, just need a formula to calculate the total possible combinations.  I've tried using nested for loops and $count++ but I found out the hard way that would take longer than I would like....quite a bit longer.  Thanks.

[neylitalo]

This is solved by a bit of very simple math:

 

<?php

$sets = 0; 

$chars = 26;
$min = 3; 
$max = 4; 

$current_length = $min;

while($current_length <= $max)
{
    $sets += pow($chars, $current_length);
    $current_length++;
}

echo "Current string length: " . ($current_length - 1) . "\n";
echo "Number of combinations: " . $sets . "\n";

?>

 

And it's fast, too. Be prepared for some very large numbers, though.

[Stooney]

Thanks neylitalo.  I cheated my way through Algebra in high school, so excuse my inability to figure this out.  But how do I 'convert' this number 8.04857523954E+28 into something like 43,000,000,000,000...  Like get rid of the E, which I assume is some sort of scientific abbreviation.

[unsider]

Just curious, sorry for the irrelevance, but...

 

how do you cheat your way through math..?

[Stooney]

Copy the smart kids work.  Needless to say I wish I hadn't now. 

[unsider]

Oh, but I'm curious on tests? you couldn't blantantly cheat right there in class, copying homework, worksheets, etc.. can only get you so far.

 

Ya it's bad thing to waste. It's getting so much harder (seems that way), pre-calculus with a hard teacher is a real challenge.

[Stooney]

Well with tests we were usually allowed to use graphing calculators.  I was able to program mine as we went over each lesson to solve all the problems for me.  So without learning the material, I was able to get correct answers.  I was from time to time docked points for not showing my work, but my teachers didn't really care if you learned, just as long as their students got good grades which made them look like good teachers.  New Mexico school system isn't the best.

[unsider]

Oh, I see, well that sucks.

 

Now that I've derailed this thread enough, I'll let you get back to the real question.

 

Sorry bout that

[Daniel0]

Thanks neylitalo. I cheated my way through Algebra in high school, so excuse my inability to figure this out. But how do I 'convert' this number 8.04857523954E+28 into something like 43,000,000,000,000... Like get rid of the E, which I assume is some sort of scientific abbreviation.

 

printf('%d', $num);

[neylitalo]

Thanks neylitalo.  I cheated my way through Algebra in high school, so excuse my inability to figure this out.  But how do I 'convert' this number 8.04857523954E+28 into something like 43,000,000,000,000...  Like get rid of the E, which I assume is some sort of scientific abbreviation.

 

"E" or "e", in a number like this, can be replaced with "* 10^". So in this case, 8.04857523954E+28 is 8.04857523954 * 10^28. This comes out to, approximately:

 

80 485 752 395 400 000 000 000 000 000

 

But if you need the exact answer, use the number_format function when you echo the final result.

 

number_format($sets);

[Stooney]

Ty both.  I was assuming the result of 64 chars, at lengths of 3-16 was in the trillions.  Apparently it's in the toomanydrillions for me to say.

 

(imma guess 80 octrillian)

80,485,752,395,443,132,135,108,509,696

[Daniel0]

It's actually called an octillion.

[Barand]

Isn't the formula for combinations of r from n items given by

 

[pre]

            n!

nCr  =  ---------

        r! (n-r)!

[/pre]

 

and the no of permutations

 

[pre]

          n!

nPr  =  ----

        (n-r)!

[/pre]

[neylitalo]

Barand: Those look correct, but they only apply if each item can only appear once in the set. This situation requires that you allow repeating elements in the list, so a factorial isn't quite what we're looking for here.

 

Probability theory is tied directly to this. Two independent events A and B have a probability of co-occurrence of P(A)*P(B). (Two mutually exclusive events A or B have a probability of occurring of P(A) + P(B), which is similar to what a factorial is describing. P(A) + P(B) + P© + P(D) ...) The number of possible outcomes is very easy to determine, from the probability - remember, a probability is just the odds of one particular outcome happening, out of all possible outcomes. When you flip a coin, it can land one of two ways, so the probability is 1/2. When you roll a die, it can land one of six ways, so the probability is 1/6. This number is the probability that one specific event (roll a 6) will happen out of all possible outcomes.

 

And since there is not more than one option per slot (we can't pick "ab" as a character - only one at a time), we can come to the conclusion that the number of possible outcomes is simple the inverse of the probability. (If it were something like "the odds of rolling a six or a three", the probability would be 2/6, or 1/3, so the inverse of the probability is not accurate here.)

 

So we can rewrite our problem like this:

 

There are 64 possible elements, A-Z, a-z, 0-9.

 

A) What is the probability of choosing an "A"?          1/64

B)What is the probability of choosing an "A" and then a "B"?              (1/64)^2

C) How many possible outcomes are there if you are going to randomly fill a list n characters long?            64^n

[TheFilmGod]

Barand: Those look correct, but they only apply if each item can only appear once in the set. This situation requires that you allow repeating elements in the list, so a factorial isn't quite what we're looking for here.

 

How does nCr not fulfill those requirements? It allows all elements to repeat themselves...?

[Barand]

@neylitalo,

 

Like regex with PHP, probability theory in maths always eluded my grasp. Things like

 

There are 64 possible elements, A-Z, a-z, 0-9.

 

were always a source of confusion.

[neylitalo]

I took the author's numbers for granted, but the ideas are the same.

 

Barand: Those look correct, but they only apply if each item can only appear once in the set. This situation requires that you allow repeating elements in the list, so a factorial isn't quite what we're looking for here.

 

How does nCr not fulfill those requirements? It allows all elements to repeat themselves...?

 

Combinations do not allow for repeating elements. If you have four letters a, b, c, and d, the possible three-letter combinations are abc, abd, acd, and bcd. One fundamental rule of combinations and permutations is that once an element is chosen, it is removed from the set of available elements.

[Barand]

I understood what you said, just having a bit of fun with the count thing.

 

Things that I have problems with are:

 

I know that if you have a group of about 30 people then it's odds on that two of them will have the same birthday (month/day), but I don't have a clue how to go about proving it.

 

or another "odds on" bet

 

in the next 20 cars passing in the opposite direction two will have the same last two digits on the licence plate

 

Anyway, treat these as rhetorical - I don't mean to hijack the thread.

[Stooney]

Hijack away.  Question was answered and the topic is interesting.