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

だから私は2つの質問があります：1）2番目のアルゴリズムにもキャッシュを実装することは可能ですか？はいの場合、これを行うのを手伝っていただけませんか。2）2番目のアルゴリズムの結果を文字列ではなく構造化配列に書き込むことは可能ですか？

あなたが私を助けてくれることを願っています。事前にどうもありがとうございました！

PS：simonnとDan Dyerの2つの機能に感謝します！

4

3 に答える 3

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 に答える
1
  1. いいえ、実際には同じ計算を 2 回実行することはないため、ここではキャッシュが役立つとは思いません。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 に答える
0

これは少し古いですが、パーティション/順列/組み合わせなどを含むさまざまな組み合わせ/シミュレーション方法を効率的に実装する PHP クラスです。

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

PS: 私は著者です

于 2013-07-22T21:13:28.407 に答える