2
\$\begingroup\$

I recently wanted to determine the probability of generating a colliding string, given a character pool size, string length and number of strings to generate. I was led to the Birthday Problem, and came up with this code in PHP:

function collision_probability($length, $count = 1) {

    $chars = '1234567890qwertyuiopasdfghjklzxcvbnm';

    $probability = 1.0;

    // Maximum number of combinations
    $combinations = pow(strlen($chars), $length);

    echo "$combinations combinations at $length characters long for $count tries\n";

    foreach(range(1,$count) as $i) {
        $probability = $probability * (1 - ($i/$combinations));
    }

    $probability = 1 - $probability;
    echo "A total probability their being collisions of ".($probability*100). "%\n";

    return $probability;

}

echo collision_probability(9, 3000000);

Given the echos, and the values you can see, am I interpreting this correctly? Or am I missing something?

\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

Instead of: $chars = '1234567890qwertyuiopasdfghjklzxcvbnm'; ...
You could do:

$alphabet = array_merge(range(0, 9), range('a', 'z'));

$combinations = pow(count($alphabet), $length));
\$\endgroup\$
2
\$\begingroup\$

Nitpicks

$chars = '1234567890qwertyuiopasdfghjklzxcvbnm';

I would find this easier to read if it were in alphabetical order.

$chars = '1234567890abcdefghijklmnopqrstuvwxyz';

That way I can see that are no letters missing.

$alphanumeric_alphabet = '0123456789abcdefghijklmnopqrstuvwxyz';

I think that makes it clearer what the string is. Also, I prefer to name scalars (numbers, strings, etc.) with singular names. I'd name $combinations $combination_count for the latter reason.

$probability = 1.0;

This is the probability that you can select the first combination without a collision.

foreach(range(1,$count) as $i) {

This is neat, but PHP doesn't handle it well. It will create the whole array and then iterate over the array.

for ( $i = 1; $i <= $count; $i++ ) {

This is more efficient in PHP.

Mathematics

However,

for ( $i = 1; $i < $count; $i++ ) {

is probably more correct. Remember that the probability of finding a combination without a collision is 1.0. So the first iteration through the loop is the 2nd, and the $count iteration is the $count + 1 combination.

Now, if instead of the birthday problem, you are looking for the chance of a match to an already existing combination, then this would be closer. However, that problem would normally not care about collisions in the match tries. So it seems you should either change the upper limit in the for loop or swap out the loop for

$probability = pow(1 - 1/$combinations, $count);

That's the chance of not matching a preexisting selection with $count tries. Note that in that case, the tries can match each other. If you want the probability of a collision:

$probability = 1 - pow(1 - 1/$combinations, $count);

More Nitpicks

Assuming the birthday problem is the right model,

    $probability = $probability * (1 - ($i/$combinations));

You could write this as

    $probability *= 1 - ($i/$combinations);

Which seems simpler. Note that the parentheses around the division are unnecessary as division is higher precedence than subtraction. Not normally a big deal either way. They do slow down the loop slightly though, so if you have performance issues, you could try removing them. With high enough iterations, it could shave off noticeable time.

echo "A total probability their being collisions of ".($probability*100). "%\n";

You misspelled "there":

echo "Total probability there being collisions of ".($probability*100). "%\n";
\$\endgroup\$
2
  • \$\begingroup\$ The example for the chance of matching a preexisting selection does not seem to work, it only ever seems to give 100%: ideone.com/ia20OU \$\endgroup\$
    – Mike
    Commented Jan 14, 2015 at 21:41
  • \$\begingroup\$ @MichaelJMulligan You round to two decimal places but the answer is 99.999997035705% which rounds to 100%. And I misstated what the formula did, which may have misled your use. I think that you still want the $probability = 1 - $probability. \$\endgroup\$
    – Brythan
    Commented Jan 15, 2015 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.