算法计算出100个组合的个数

我希望这不是家庭作业问题!

    def combinations(n: Int, step: Int, distance: Int, sum: Int = 100): List[List[Int]] =
      if (n == 1) 
        List(List(sum))
      else 
        for {
          first <- (step until sum by step).toList
          rest <- combinations(n - 1, step, distance, sum - first)
          if rest forall (x => (first - x).abs <= distance)
        } yield first :: rest

如果需要将100除以2,最大距离为N,则组合中的最小值为

如果您需要将100除以3个值,最大距离为N,这将变得更加棘手。3个值的平均值是100/3,但是如果其中一个值比这个平均值低很多,那么另一个值只能略大于这个平均值,这意味着最小值不是平均值减去最大距离除以2,而是可能的

一般来说,对于M值,这将成为

100/米-(M-1)牛/米

(100-(M-1)N)/M

同样,我们可以计算出可能的最高值:

这将为组合的第一个值提供一个范围。

要确定第二个值的范围,必须考虑以下约束:

• 第一个值的距离(不应大于最大距离)
• 我们还能达到总数(100)吗

假设我们用10的倍数将100除以3,最大距离为30 如前所述,最小值为:

最大值为

所以对于第一个值,我们应该迭代20,30,40和50。

假设我们选20个。剩下的两个值是80。 同样,我们可以在最大距离为30的2个值上分布80,这给出:

最小值:(80-(2-1)30)/2-->25-->四舍五入-->30

第二个约束是,与第一个值相比,我们不希望距离大于30。这将给出最小值-10,最大值50。

现在取两个域之间的交集-->30到50,第二个值迭代30,40,50。

然后对下一个值重复此操作。

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}

N-组合数 M-倍数 D-最大可能距离

所以组合中可能的值可以是M,2M,3M等等。您需要生成这个集合,然后从集合中的第一个元素开始,并尝试从同一集合中选择值来找出下两个元素(前提是它们与第一个/第二个值的距离应小于D)。 所以当i/p为3-10-30时

1. 创建一组10、20、30、40、50、60、70、80、90作为可能的值
2. 从10开始,第二个值的选择必须是20、30、40、50(D<30)
3. 现在从20、30、40、50中选择第二个值,然后尝试获取下一个值,依此类推

如果您使用递归,那么解决方案将变得更加简单。

1. 你必须从一个 最小值内可能值的列表; 最大索引。
2. 所以先试试这个值 选择了X索引的值。
3. 对于每个第一个值,尝试找到 从列表中输出N-1个值,其中MIN=

当M=1且N足够大时,性能最差。

之间的距离 全部的 加性因素,或 他们中的一个?例如,对于3-10-20,[20-40-60]是有效答案吗?我假设是后者,但是可以对下面的解决方案进行非常简单的修改,以适用于前者。

无论如何,方法是从你能处理的最极端的答案开始,然后沿着答案走,直到你到达另一个最极端。

让我们试着把数字尽可能低,除了最后一个,这将是尽可能高(鉴于其他人是低)。让公约数为 d 分而治之 100 S = 100/d s ,除非我们把它转换成一系列的量子化步骤, n = s/d . 现在假设我们有 M 样品, i1...iM 并写出约束条件:

i1 + i2 + i3 + ... + iM = S
0 <= i1 <= n
0 <= i2 <= n
. . .
0 <= iM <= n
i1 <= i2
i2 <= i3
. . .
i(M-1) <= iM

我们可以解出第一个方程 iM 考虑到其他人。

现在,如果我们让一切尽可能相似:

i1 = i2 = ... = iM = I
M*I = S
I = S/M

I 是一个分数,做前几个 I+1 )现在我们试着依次遍历每个变量:

for (i1 = I-1 by -1 until criteria fails)
  sum needs to add to S-i1
  i2 >= i1
  i2 <= i1 +n
  solve the same problem for M-1 numbers adding to S-i1
  (while obeying the above constraint on i2)

好吧,看这里——我们有一个递归算法!我们只是走一遍,然后读出答案。

当然,我们可以走路 i1 向上而不是向下。如果你需要打印答案,不妨这样做。如果你只需要对它们进行计数,请注意,向上计数是对称的,所以只需将从向下计数得到的答案加倍。(如果不是所有值的起始值都相同,那么也会有一个校正系数——如果有些值是相同的 我 有些是 我+1 ,你需要考虑到这一点,我不会在这里做。)

编辑:如果范围是每个值必须适应的范围,而不是所有

0 <= i1 <= n

条件,你有

max(i1,i2,...,iM) - min(i1,i2,...,iM) <= n

但这给出了相同的递归条件,只是我们传递了那些我们已经选择要放入到混合中的项的最大值和最小值,而不是对它们添加约束 i2 (或其他变量的轮值)。

输入: (2-10-20)

(50,50)

例如:abs(50-50)<20,这样就可以了

3将第一个值增加param 2,将第二个值减少param 2

4. 开始2。指向