Permutations

The other day a friend was seeking advice about passwords and password length and such and I just told him the strength of a password is based on however many characters (n) he has available to him to the power of the length of the string (l), n^l, and that he should also use non-alphanumeric characters as well and make sure it's long enough and memorable to him. Using the formula, a 4 letter password using just digits is 10^4, or 10000 possible combinations.

That got me thinking about cracking and finding combinations of passwords if you know which characters were used and in what frequency. Basically you would need to jumble the characters up and try the different combinations but because you know which characters were used the entropy is far less, l^2 - l. This would mean a 4 letter passwords using the characters abcd would have 4^2 - 4, or 12 possible combinations.

I had to put a little thought into how I was going to code this. The first thing you do when you have to write an algorithm is figure out how you would do it in real life and I thought up the idea of swivelling characters round. So, if we have the starting characters abcd, you would lock the first character and swivel the other three round:

abcd
adbc
acdb

Then, you would shift the first character (a) off the original array and push it onto the end, lock the new first character (b), and do the swivelling of the other three again:

bcda
bacd
bdac

and so on. So when I first tried to solve this problem I did it the easy way by using the php array functions:

<?php

/**
 * Produce permutations of a string using php array functions
 * @author Ahmad Retha
 * @license public domain
 */

$s = "abcd"; //starting letters
$a = str_split($s); //converted to char array
$l = count($a); //length of array
$i = 0; //initialize counter for loop
$r = array(); //result array holds the combinations

while ($i < $l) {
   
    $b = array_slice($a, 1); //new array missing first element
    $j = 0; //initialize counter for inter-swivel
    while ($j < $l - 1) {
        array_push($b, array_shift($b)); //swivel smaller array
        //store result in $r
        $r[] = implode('', array_merge((array)$a[0], $b));
        $j++;
    }
   
    array_push($a, array_shift($a)); //swivel initial character
   
    $i++;
}
?>

But I was not satisfied with this and set about rewriting it in a more efficient way using array index manipulation to move elements around. This code is a little longer but more efficient and runs a tad faster:

<?php

/**
 * Produce permutations of a string through array manipulation
 * @author Ahmad Retha
 * @license public domain
 */

$s = "abcd"; //starting letters
$a = str_split($s); //converted to char array
$l = count($a); //length of array
$r = array(); //result array holds the combinations
$c = 0; //counter
$t = null; //temporarily holds first char

while ($c < $l) {

    $t = $a[0]; //store first char

    $n = 1; //initialize counter for inner loop

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

        while ($n < $l) {
            //temporarily store first char of inner substring
            $u = $a[1];
           
            //shift chars along in substring
            for ($j = 2; $j < $l; $j++) {
                $a[$j - 1] = $a[$j];
            }
           
            $a[$l - 1] = $u; //push substring temp char to end
           
            $r[] = implode('', $a); //store the permutation
           
            $n++;
        }
        
        //shift chars along in whole string
        $a[$i - 1] = $a[$i];
    }

    $a[$l - 1] = $t; //push temp char to end

    $c++;
}

?>


This is sample output of the 12 combinations held in $r:

acdb
adbc
abcd
bdac
bacd
bcda
cabd
cbda
cdab
dbca
dcab
dabc