정수의 부등호 파티션을 찾는 효율적인 방법

Question

정수의 총 파티션이 있고 모든 값이 동일하지 않은 파티션 만 필요합니다. 예를 들어 - 3의 파티션은 {1,1,1,1}, {2,2}, {3,1}, {1,1,2} 및 {4}입니다. 따라서, 불평등 분할 영역은 등가 요소가 없기 때문에 {3,1}과 {4}가 필요합니다. 모든 파티션을 찾는 데 사용한 코드는 다음과 같습니다. 원하는 결과를 얻으려면 파티션을 필터링 할 수 있지만 모든 파티션을 찾지 않고 동일한 용어가없는 모든 파티션을 찾는 효율적인 방법을 원합니다. 나는 그물과 stackoverflow하지만 아무것도 정확하게 내가 직면하고있는 문제를 검색했습니다. 모든 아이디어는 높이 평가됩니다. 감사.

function total_partitions_of_a_number($n) {# base case of recursion: zero is the sum of the empty list 
if(!$n) return array(array()); # return empty array 

# modify partitions of n-1 to form partitions of n 
foreach(total_partitions_of_a_number($n-1) as $p) { # recursive call 
$a[] = array_merge(array(1), $p); # "yield" array [1, p...] 
if($p && (count($p) < 2 || $p[1] > $p[0])) { # p not empty, and length < 2 or p[1] > p[0] 
    ++$p[0]; # increment first item of p 
    $a[] = $p; # "yield" p 
} 
} 
return $a; # return all "yielded" values at once 
} 

Answer 1

주어진 구성 요소가 두 번 이상 나타나는 파티션 만 원하십니까? 재귀는 간단합니다.

N의 파티션에 대한 문제를 줄이면 세트의 어떤 요소도 어떤 값보다 큽니다 (처음에는 N이됩니다). 이제는 파티션에 나타나거나 나타나지 않습니다 . 이것에 따라, (N-a)의 파티션을 재귀 적으로 풀어 어떤 요소도 a-1보다 크지 않게하고, N의 파티션에서 어떤 멤버도 a-1보다 크지 않도록 반복적으로 풀어줍니다.

어느 경우이든, 재귀는 문제가 해결되지 않을 때 종료 될 것이므로 a * (a + 1)/2 < N 일 때 끝납니다. 물론 * (a + 1)/2 = N이면 솔루션이 고유하기 때문에 신속하게 재귀를 종료 할 수 있습니다.