CODEWITHSUNDEEP
phpfunctionpartitioningcombinatorics
caw
caw

Reputation: 31487

PHP: Caching ordered integer partition algorithm

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!

Upvotes: 1

Views: 931

Answers (3)

Nikos M.
Nikos M.

Reputation: 11

Although this is a bit old, nevertheless, a PHP Class which implements various combinatorics/simulation methods including partitions/permutations/combinations etc.. in an efficient way

https://github.com/foo123/Simulacra/blob/master/Simulacra.php

PS: i am the author

Upvotes: 0

OIS
OIS

Reputation: 10033

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;
}

Upvotes: 1

pix0r
pix0r

Reputation: 31280

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

Upvotes: 1

Related Questions