1

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

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

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这两个函数！

4

3 回答 3

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

尝试这样更改showPartitions()：

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);
于 2009-09-08T22:24:46.483 回答
1

题外话：我重写了第一个函数，让它更快一点。

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;
}
于 2009-09-08T23:31:26.880 回答
0

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

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

PS：我是作者

于 2013-07-22T21:13:28.407 回答