5

我有一个函数（来自未回答的上一个问题），它创建一个具有 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 和/或负整数。

4

2 回答 2

13

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

于 2010-05-08T15:22:53.030 回答
2

我会使用'三角形下的面积'公式......就像cletus（！？）我真的要开始更加关注事情......

无论如何，我认为这个解决方案现在非常优雅，它在所有元素之间均匀地应用所需的最小间距，均匀地缩放间隙（分布）以保持原始总和并且以非递归方式完成工作（排序除外）：

给定一个长度为 n 的随机数数组 a()

生成排序索引 s()

并处理排序间隔 a(s(0))-a(s(1))、a(s(1))-a(s(2)) 等

  1. 将每个间隔增加所需的最小间隔大小，例如 1（这必然会扭曲它们的“随机性”）

  2. 将每个间隔减少一个计算出来的因子，以将系列总和恢复到没有添加间距的值。

如果我们将 1 添加到每个系列，我们将系列总和增加 1 * len

1 添加到每个系列间隔增加总和： len*(len+1)/2 //( ?pascal's triangle )

草稿代码：

$series($length);        //the input sequence 
$seriesum=sum($series);  //its sum
$minsepa=1;              //minimum separation

$sorti=sort_index_of($series) //sorted index - php haz function?

$sepsum=$minsepa*($length*($length+1))/2; 
//sum of extra separation

$unsepfactor100=($seriesum*100)/($seriesum+sepsum); 
//scale factor for original separation to maintain size
//(*100~ for integer arithmetic)

$px=series($sorti(0)); //for loop needs the value of prev serie

for($x=1 ; $x < length; $x++)
{ $tx=$series($sorti($x));             //val of serie to
  $series($sorti($x))= ($minsepa*$x)   //adjust relative to prev
                     + $px 
                     + (($tx-$px)*$unsepfactor100)/100; 

  $px=$tx;                             //store for next iteration 
  }
  • 所有间隔都减少一个常数（非随机扭曲因子）
  • 可以将分隔设置为 1 以外的值
  • 实施需要仔细调整（我通常测试和“校准”）
    以适应舍入误差。可能将所有内容放大约 15 倍，然后再缩小。如果处理得当，间隔应该会继续存在。

生成排序索引后，将索引的顺序打乱为重复值，以避免在碰撞序列的序列中运行。（或者如果顺序无关紧要，则只是打乱最终输出）

洗牌骗子的索引：

for($x=1; $x<$len; $x++)                   
{ if ($series($srt($x))==$series($srt($x-1)))
  { if( random(0,1) ) 
    { $sw= $srt($x);
      $srt($x)= $srt($x-1);
      $srt($x-1)= $sw;
  } } }

可以对“随机序列”进行一种最小干扰，只需将受骗者按所需的最小值分开，而不是将它们移动得超过最小值——问题所寻求的一些“随机”数量。

这里的代码通过最小分隔来分隔每个元素，无论是否重复，这应该是一种公平的，但可能是过度的。可以修改代码以仅通过查看它们的系列（sorti（n0：n1..len））并将sepsum计算为每个骗子的+ = minsep *（len-n）来分离骗子。然后调整循环只需要在应用调整之前再次测试是否有欺骗性。

于 2010-05-09T18:45:14.347 回答