查找整数不相等分区的有效方法


efficient way to find unequal partitions of an integer

我有一个整数的总分区,我只想要那些所有值都不相等的分区。对于 ex.-Partitions of 3 是 {1,1,1,1},{2,2},{3,1},{1,1,2} 和 {4}。因此,所需的不相等分区是 {3,1} 和 {4},因为它们不包含相等的元素。下面提供了我用于查找所有分区的代码。我可以过滤分区以获得所需的结果,但我想要一些有效的方法来查找所有分区,这些分区中没有相等的项,而无需找到所有分区。我已经搜索了网络和堆栈溢出,但没有确切说明我面临的问题。每个想法都受到赞赏。谢谢。

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
}

所以你只想要任何给定组件出现不超过一次的分区?递归很简单。

将其简化为求解 N 的分区的问题,这样集合中没有元素大于某个值 a(a 最初为 N)。现在,分区中要么出现,要么不出现。根据这一点,您将递归求解 (N-a) 的分区,使得没有元素大于 a-1,以及 N 的分区,使得没有成员大于 a-1。

在任何一种情况下,递归都是很好的,并且当不再可能解决问题时,递归将终止,因此,当 a*(a+1)/2