1

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!

Improve this question

3 Answers 3

Reset to default
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);
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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;
}
Improve this answer

6 Comments

Thank you so much, OIS! :) Your function isn't "a little bit faster". In my test runs, it has been 43 times as fast as my old function! I can't believe this. How did you do this? Is while faster than for? Why did you write the "static" in front of the array declaration?
If I use a global variable instead of the declaration of the array in the function itself, it's only 2 times as fast as my old function. So the good performance depends mainly on this array. Why is this?
@marco92w: static means it is "saved" for all functions (or class instances in a class). If you change static to global without removing the = array() initiation you have basically removed the cache functionality because you overwrite the variable with an empty array with each recursion. If you want to be able to access the cache variable, you should make this function a static method part of a class, with the cache a static variable of the class.
@marco92w: it is faster because I have calulated everything which give the same result outside of the loop, and I save the cache with numeric keys instead of creating a string.
@marco92w: I do not use global variables if I can help it, so I have not thought about it. Some things are a bit faster. Might be the reason is that the static variable in the function is saved closer in memory with the function, while it has to look up the global variable. Improving a benchmark code, I noticed I should make constants into static variables to speed up repeated function calls.
|
0

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.