我下面有一个函数来自上个未解决的问题,该函数创建了一个具有n个值的数组。数组的总和等于$ max。
function randomDistinctPartition($n, $max) { $partition= array(); for ($i = 1; $i < $n; $i++) { $maxSingleNumber = $max - $n; $partition[] = $number = rand(1, $maxSingleNumber); $max -= $number; } $partition[] = $max; return $partition; }
例如:如果我设置$ n = 4和$ max =30。那么我应该得到以下内容。
array(5, 7, 10, 8);
但是,此功能未考虑重复项和0。我想要并且一直在尝试实现的是,生成一个具有 唯一 数字的数组,这些数组加起来等于我的预定变量 $ max 。 没有重复的数字 , 没有0和/或负整数 。
好的,这个问题实际上与线性序列有关。最小值为1时,请考虑以下顺序:
f(n) = 1 + 2 + ... + n - 1 + n
这样一个序列的总和等于:
f(n) = n * (n + 1) / 2
因此,对于n = 4,例如,总和为10。这意味着,如果选择4个不同的数字,则没有零且没有负数的最小总数为10。现在反过来:如果总数为10,且4个数字,则只有(1,2,3,4)的一种 组合 。
因此,首先您需要检查总数是否至少等于此下限。如果小于,则没有组合。如果相等,则只有一种组合。如果更高,它将变得更加复杂。
现在想象一下,您的约束总共是12个,包含4个数字。我们已经确定f(4)=10。但是,如果第一个(最低)数字为2,该怎么办?
2 + 3 + 4 + 5 = 14
因此,第一个数字不能大于1。您知道您的第一个数字。现在,您将生成一个由3个数字组成的序列,总数为11(即12-1)。
1 + 2 + 3 = 6 2 + 3 + 4 = 9 3 + 4 + 5 = 12
第二个数字必须为2,因为它不能为1。它不能为3,因为以3开头的三个数字的最小和为12,我们必须加到11。
现在我们发现两个数字加起来等于9(12-1-2),其中3是可能的最小值。
3 + 4 = 7 4 + 5 = 9
第三个数字可以是3或4。找到的第三个数字是固定的。两种可能的组合是:
1, 2, 3, 6 1, 2, 4, 5
您可以将其转换为通用算法。考虑以下递归实现:
$all = all_sequences(14, 4); echo "\nAll sequences:\n\n"; foreach ($all as $arr) { echo implode(', ', $arr) . "\n"; } function all_sequences($total, $num, $start = 1) { if ($num == 1) { return array($total); } $max = lowest_maximum($start, $num); $limit = (int)(($total - $max) / $num) + $start; $ret = array(); if ($num == 2) { for ($i = $start; $i <= $limit; $i++) { $ret[] = array($i, $total - $i); } } else { for ($i = $start; $i <= $limit; $i++) { $sub = all_sequences($total - $i, $num - 1, $i + 1); foreach ($sub as $arr) { array_unshift($arr, $i); $ret[] = $arr; } } } return $ret; } function lowest_maximum($start, $num) { return sum_linear($num) + ($start - 1) * $num; } function sum_linear($num) { return ($num + 1) * $num / 2; }
输出:
All sequences: 1, 2, 3, 8 1, 2, 4, 7 1, 2, 5, 6 1, 3, 4, 6 2, 3, 4, 5
一种实现是获取所有序列并随机选择一个。这样做的好处是可以对所有可能的组合进行平均加权,这对于您正在执行的操作可能有用或不必要。
如果元素总数大或数量大,将变得笨拙,在这种情况下,可以对上述算法进行修改,以返回从$start到$limit而不是每个值的范围内的随机元素。
$start
$limit