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) 두 번째 알고리즘의 결과를 문자열 대신 구조화 된 배열에 쓸 수 있습니까?

도와 주시면 감사하겠습니다. 대단히 감사드립니다!

추신 : 두 가지 기능, Simonn과 Dan Dyer에게 감사드립니다.

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

및 그것은 빈 배열 :

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 : 저는 저자입니다