Permutations Script Needs Optimization

Question

I have functions of permutation :

function permutations($letters,$num)
{
   $last = str_repeat($letters[0],$num);
   $result = array();
   while($last != str_repeat($this->lastchar($letters),$num))
   {
       $result[] = $last;
       $last = $this->char_add($letters,$last,$num-1);
   }
   $result[] = $last;
   return $result;
}

function char_add($digits,$string,$char)
{
    error_reporting(0);

    if($string[$char] < $this->lastchar($digits))
    {
       $string[$char] = $digits[strpos($digits,$string[$char])+1];
       return $string;
    }
    else
    {
       $string = $this->changeall($string,$digits[0],$char);
       return $this->char_add($digits,$string,$char-1);
    }
}

function lastchar($string)
{
   return $string[strlen($string)-1];
}

function changeall($string,$char,$start = 0,$end = 0)
{
   if($end == 0) $end = strlen($string)-1;
   for($i=$start;$i<=$end;$i++){
       $string[$i] = $char;
   }
   return $string;
}

Example to run this :

print_r($this->permutations('1234',2));

And results will be:

Array(
[0] => 11
[1] => 12
[2] => 13
[3] => 14
[4] => 21
[5] => 22
[6] => 23
[7] => 24
[8] => 31
[9] => 32
[10] => 33
[11] => 34
[12] => 41
[13] => 42
[14] => 43
[15] => 44)

It can run well. However, when I run with greater number of permutation like : $this->permutations('1234',5) , the script will cause memory exhaustion.

What can I change to optimize the functions ?

Answer 1

I've approached it from a hint @hacatu said, that you are storing all the permutations in an array. I thought move this to a generator, although I think trying out Heap's algorithm could be beneficial too.

I'm only adding the function that has changes, the rest of the code stayed the same. When using generators, you don't need to build up a whole array, you get an Generator object which implements the Iterator interface. The execution of your code stops at the yield statement and only continue if next() is called ie in a foreach

function permutations($letters,$num)
{
    $last = str_repeat($letters[0],$num);
    // no result array
    while($last != str_repeat($this->lastchar($letters),$num))
    {
        yield $last; // <-- one change
        $last = $this->char_add($letters,$last,$num-1);
    }

    yield $last; // <-- another change
}

I've put these methods in a class called Permutation and used it like this:

$perm = new Permutation();
$perms = $perm->permutations('1234', 10); // $perms is a Generator object here

// I'm looping through the results, if needed you can build up an array here, but that will need a lot of memory as you already seen
foreach ($perms as $result) {
    printf("%s\n", $result);
}

printf("Max memory: %sK\n", number_format(memory_get_peak_usage(true)/1024));

When I run this code (as it doesn't do much just prints) it ends up printing me:

lots of permutations here
....
4444444444
Max memory: 2,048K

When I add all the permutations to an array, the memory usage jumps

lots of permutations here
....
4444444444
Max memory: 75,780K

I hope this helps.

Ps: If you are into JavaScript and redux have a look at redux-saga, it can also help understanding generators. If not, I hope the PHP docs will help you :)