php - 找到整数的不相等分区的有效方法

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 的分区的问题，使得集合中没有元素大于某个值 a(a 最初为 N。)现在，a 出现或不出现在分区中。根据这一点，您将递归地求解 (N-a) 的分区，使得没有元素大于 a-1，以及 N 的分区，使得没有成员大于 a-1。

无论哪种情况，递归都是适定的，并且当不再可能解决问题时终止，因此，当 a*(a+1)/2 < N 时。当然，当 a*(a +1)/2 = N，您也可以快速终止递归，因为解决方案是唯一的。