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

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,因为它不能是一个.它不能是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不是每个值的随机元素.