0
\$\begingroup\$

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 ?

\$\endgroup\$
  • 2
    \$\begingroup\$ This question can't be answered on the basis of the available information. What is the spec? It seems to be to generate Cartesian powers, but e.g. how should it handle repetition? \$\endgroup\$ – Peter Taylor Jun 30 '16 at 15:40
  • 1
    \$\begingroup\$ Most of the time, the best way to generate permutations is to use Heap's algorithm. The main problem with your code is that it stores all permutations, which requires O(n*n!) memory and is not practical. You need to not do this, and some ways to avoid it include using a lazy generator, using a callback, or baking Heap's algorithm into your function. \$\endgroup\$ – hacatu Jul 1 '16 at 0:23
  • \$\begingroup\$ ini_set('memory_limit', '1G'); is a temporary fix. \$\endgroup\$ – 54 69 6D Jul 3 '16 at 21:57
  • \$\begingroup\$ increase the memory limit still won't be enough when doing larger permutation \$\endgroup\$ – oit oit Jul 5 '16 at 4:35
2
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ Woah, this indeed reduces the memory usage. I tested it with 6 digit numbers with 6 combination and it reduces the memory by 33%. Thank you so much! \$\endgroup\$ – oit oit Feb 20 '17 at 3:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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