0

我有一个整数的总分区，我只想要那些所有值都不相等的分区。例如，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
}
4

1 回答 1

2

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

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

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

于 2012-04-07T12:28:10.593 回答