php - 用随机生成的新值替换数组中的重复值

Question

我在下面有一个函数(来自未得到答复的 previous question)，它创建了一个包含 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和/或负整数。

Answer 1

好的，这个问题实际上是围绕线性序列展开的。考虑序列的最小值 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< 范围内的随机元素 而不是每个值。