PHP：缓存有序整数分区算法

Question

第一：该问题在维基百科中的名称是“集合的有序划分”。

我有一个计算可能分区的算法。为了加快速度，我使用了缓存：

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

此外，我还有另一种算法，它显示这些可能的分区的列表。但它还没有使用缓存，所以速度很慢：

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

所以我有两个问题： 1）第二种算法是否也可以实现缓存？如果是的话，你能帮我做到这一点吗？ 2）是否可以将第二个算法的结果写入结构化数组而不是字符串？

我希望你能帮助我。预先非常感谢您！

PS：感谢 simonn 和 Dan Dyer 的两位贡献！

Answer 1

1. 不，我认为缓存不会对您有帮助，因为您实际上永远不会执行两次相同的计算。每次调用 showPartitions() 都有不同的参数并生成不同的结果。
2. 是的当然。您基本上是使用另一层指向整数的嵌套数组来替换由管道字符分隔的字符串。 （您将拥有 array(array(1), array(2), array(3))，而不是“A|B|C”。）

尝试更改 showPartitions() code> 如下：

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

不要使用 $prefix 的空字符串来调用它，而是使用空数组来调用它：

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

Answer 2

题外话：我重写了第一个函数，使其速度更快一点。

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

Answer 3

虽然这个有点老了，但是，
一个 PHP 类，它以有效的方式实现各种组合/模拟方法，包括分区/排列/组合等

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

PS：我是作者