PHP: Caching ordered integer partition algorithm

Question

Hello!

First: The problem's name in Wikipedia is "ordered partition of a set".

I have an algorithm which counts possible partitions. To speed it up, I use a cache:

function partition($intervalSize, $pieces) {
 // special case of integer partitions: ordered integer partitions
 // in Wikipedia it is: ordered partition of a set
 global $partition_cache;
 // CACHE START
 $cacheId = $intervalSize.'-'.$pieces;
 if (isset($partition_cache[$cacheId])) { return $partition_cache[$cacheId]; }
 // CACHE END
 if ($pieces == 1) { return 1; }
 else {
  $sum = 0;
  for ($i = 1; $i < $intervalSize; $i++) {
   $sum += partition(($intervalSize-$i), ($pieces-1));
  }
  $partition_cache[$cacheId] = $sum; // insert into cache
  return $sum;
 }
}
$result = partition(8, 4);

Furthermore, I have another algorithm which shows a list of these possible partitions. But it doesn't use a cache yet and so it's quite slow:

function showPartitions($prefix, $start, $finish, $numLeft) {
 global $partitions;
 if ($numLeft == 0 && $start == $finish) { // wenn eine Partition fertig ist dann in Array schreiben
  $gruppen = split('\|', $prefix);
  $partitions[] = $gruppen;
 }
 else {
  if (strlen($prefix) > 0) { // nicht | an Anfang setzen sondern nur zwischen Gruppen
   $prefix .= '|';
  }
  for ($i = $start + 1; $i <= $finish; $i++) {
   $prefix .= chr($i+64);
   showPartitions($prefix, $i, $finish, $numLeft - 1);
  }
 }
}
$result = showPartitions('', 0, 8, 4);

So I have two questions: 1) Is it possible to implement a cache in the second algorithm, too? If yes, could you please help me to do this? 2) Is it possible to write the results of the second algorithm into an structured array instead of a string?

I hope you can help me. Thank you very much in advance!

PS: Thanks for the two functions, simonn and Dan Dyer!

Answer 1

1. No, I don't think a cache will help you here because you're never actually performing the same calculation twice. Each call to showPartitions() has different parameters and generates a different result.
2. Yes, of course. You're basically using another level of nested arrays pointing to integers to replace a string of characters separated by pipe characters. (Instead of "A|B|C" you'll have array(array(1), array(2), array(3)).)

Try changing showPartitions() as such:

if ($numLeft == 0 && $start == $finish) { // wenn eine Partition fertig ist dann in Array schreiben
 $partitions[] = $prefix;
}
else {
 $prefix[] = array();
 for ($i = $start + 1; $i <= $finish; $i++) {
  $prefix[count($prefix) - 1][] = $i;
  showPartitions($prefix, $i, $finish, $numLeft - 1);
 }
}

and instead of calling it with an empty string for $prefix, call it with an empty array:

showPartitions(array(), 0, 8, 4);

Answer 2

Off topic: I rewrote the first function to be a little bit faster.

function partition($intervalSize, $pieces) {
    // special case of integer partitions: ordered integer partitions
    // in Wikipedia it is: ordered partition of a set

    // CACHE START
    static $partition_cache = array();
    if (isset($partition_cache[$intervalSize][$pieces])) { 
     return $partition_cache[$intervalSize][$pieces];
    }
    // CACHE END

    if ($pieces === 1) {
     return 1;
    } 
    if ($intervalSize === 1) {
     return 0;
    }

    $sum = 0;
    $subPieces = $pieces - 1;
    $i = $intervalSize;
    while (--$i) {
      $sum += partition($i, $subPieces);
    }
    $partition_cache[$intervalSize][$pieces] = $sum; // insert into cache
    return $sum;
}