获取给定数字的所有可能组合以达到给定的总和

html5 • • 问答

我有 5 个数字1、2、3、4和5，我想得到这些数字的所有可能组合，以达到给定的总数10。

例子：

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + = 10
1 + 2 + 2 + 3 + 2 = 10
7 + 3 = 10
4 + 5 + 1 = 10
2 + 2 + 2 + 1 + 3 = 10
and so on...

如果这里有人可以就如何解决这个问题给出一个很好的解决方案，我将不胜感激？

回答

虽然这可以说不是一个 Delphi 问题而是一个关于纯数学的问题，但我可以给你一些提示。

首先，请注意总和中显然不能超过 10 个项，因为如果您有 10 个以上的项，那么您至少有 11 个项，因此总和变为至少

11 × Lowest allowed summand = 11 × 1 = 11

11 × Lowest allowed summand = 11 × 1 = 11

这已经大于 10。

因此，这个问题的单一解决方案自然可以表示为一个正好包含 10 个整数的数组，从0到5。

但是请注意，两个不同的TCandidate值可能代表相同的解决方案：

5, 3, 2, 0, 0, 0, 0, 0, 0, 0
3, 2, 5, 0, 0, 0, 0, 0, 0, 0
5, 3, 0, 0, 0, 0, 0, 0, 2, 0

5, 3, 2, 0, 0, 0, 0, 0, 0, 0
3, 2, 5, 0, 0, 0, 0, 0, 0, 0
5, 3, 0, 0, 0, 0, 0, 0, 2, 0

由于每个被加数是从一组基数 6 中选择的，因此有 6 10 = 60466176 个可能的TCandidate值。对于现代计算机，这是一个“小”数，因此即使是尝试每个此类候选者（通过计算其总和！）的非常幼稚的算法也会几乎立即给您答案。

此外，由于 10 不是一个很大的数字，您可以使用十个嵌套for循环，这种方法几乎是微不足道的（对吧？）。然而，这种方法太丑了，我拒绝使用它。相反，我将使用一种更优雅的方法，它也适用于其他值，而不是像10.

type
  TTerm = 0..5;
  TCandidate = array[0..9] of TTerm;

GetNextCandidate如果您认为候选者是基数为 6 的数字，则该函数用于按照您获得的顺序枚举候选者。它接受一个候选人, like(2, 1, 3, 0, 5, 2, 1, 3, 2, 0)并将其替换为下一个, like (2, 1, 3, 0, 5, 2, 1, 3, 2, 1), 除非你在最后一个: (5, 5, 5, 5, 5, 5, 5, 5, 5, 5)。

让我们试试这个枚举：

（实现OutputCandidateVector留作练习）产生

0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 0, 0, 0, 0, 2
0, 0, 0, 0, 0, 0, 0, 0, 0, 3
0, 0, 0, 0, 0, 0, 0, 0, 0, 4
0, 0, 0, 0, 0, 0, 0, 0, 0, 5
0, 0, 0, 0, 0, 0, 0, 0, 1, 0
0, 0, 0, 0, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 0, 0, 1, 2
0, 0, 0, 0, 0, 0, 0, 0, 1, 3
0, 0, 0, 0, 0, 0, 0, 0, 1, 4
0, 0, 0, 0, 0, 0, 0, 0, 1, 5
0, 0, 0, 0, 0, 0, 0, 0, 2, 0
0, 0, 0, 0, 0, 0, 0, 0, 2, 1
0, 0, 0, 0, 0, 0, 0, 0, 2, 2
0, 0, 0, 0, 0, 0, 0, 0, 2, 3
0, 0, 0, 0, 0, 0, 0, 0, 2, 4
0, 0, 0, 0, 0, 0, 0, 0, 2, 5
0, 0, 0, 0, 0, 0, 0, 0, 3, 0
0, 0, 0, 0, 0, 0, 0, 0, 3, 1
0, 0, 0, 0, 0, 0, 0, 0, 3, 2
0, 0, 0, 0, 0, 0, 0, 0, 3, 3
0, 0, 0, 0, 0, 0, 0, 0, 3, 4
0, 0, 0, 0, 0, 0, 0, 0, 3, 5
...

0, 0, 0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 1
0, 0, 0, 0, 0, 0, 0, 0, 0, 2
0, 0, 0, 0, 0, 0, 0, 0, 0, 3
0, 0, 0, 0, 0, 0, 0, 0, 0, 4
0, 0, 0, 0, 0, 0, 0, 0, 0, 5
0, 0, 0, 0, 0, 0, 0, 0, 1, 0
0, 0, 0, 0, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 0, 0, 1, 2
0, 0, 0, 0, 0, 0, 0, 0, 1, 3
0, 0, 0, 0, 0, 0, 0, 0, 1, 4
0, 0, 0, 0, 0, 0, 0, 0, 1, 5
0, 0, 0, 0, 0, 0, 0, 0, 2, 0
0, 0, 0, 0, 0, 0, 0, 0, 2, 1
0, 0, 0, 0, 0, 0, 0, 0, 2, 2
0, 0, 0, 0, 0, 0, 0, 0, 2, 3
0, 0, 0, 0, 0, 0, 0, 0, 2, 4
0, 0, 0, 0, 0, 0, 0, 0, 2, 5
0, 0, 0, 0, 0, 0, 0, 0, 3, 0
0, 0, 0, 0, 0, 0, 0, 0, 3, 1
0, 0, 0, 0, 0, 0, 0, 0, 3, 2
0, 0, 0, 0, 0, 0, 0, 0, 3, 3
0, 0, 0, 0, 0, 0, 0, 0, 3, 4
0, 0, 0, 0, 0, 0, 0, 0, 3, 5
...

现在我们“完成”了：

const
  FirstCandidate: TCandidate = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);

function GetNextCandidate(var ANext: TCandidate): Boolean;
begin
  for var p := High(ANext) downto Low(ANext) do
    if ANext[p] < High(TTerm) then
    begin
      Inc(ANext[p]);
      for var p2 := Succ(p) to High(ANext) do
        ANext[p2] := 0;
      Exit(True);
    end;
  Result := False;
end;

使用两个更简单的帮助程序。

输出：

...
0+3+3+0+2+0+0+1+0+1
0+3+3+0+2+0+0+1+1+0
0+3+3+0+2+0+0+2+0+0
0+3+3+0+2+0+1+0+0+1
0+3+3+0+2+0+1+0+1+0
0+3+3+0+2+0+1+1+0+0
0+3+3+0+2+0+2+0+0+0
0+3+3+0+2+1+0+0+0+1
0+3+3+0+2+1+0+0+1+0
0+3+3+0+2+1+0+1+0+0
0+3+3+0+2+1+1+0+0+0
0+3+3+0+2+2+0+0+0+0
0+3+3+0+3+0+0+0+0+1
0+3+3+0+3+0+0+0+1+0
0+3+3+0+3+0+0+1+0+0
0+3+3+0+3+0+1+0+0+0
0+3+3+0+3+1+0+0+0+0
0+3+3+0+4+0+0+0+0+0
0+3+3+1+0+0+0+0+0+3
0+3+3+1+0+0+0+0+1+2
0+3+3+1+0+0+0+0+2+1
0+3+3+1+0+0+0+0+3+0
0+3+3+1+0+0+0+1+0+2
0+3+3+1+0+0+0+1+1+1
0+3+3+1+0+0+0+1+2+0
...

但是我们如何摆脱重复呢？请注意，有两个重复来源：

  • 首先，我们有零点的位置。0+3+3+1+0+0+0+1+1+1并且0+3+3+1+0+0+1+0+1+1都写得更自然3+3+1+1+1+1。

  • 其次，我们有排序：3+3+1+1+1+1vs 3+1+3+1+1+1。

从您的问题中不清楚您是否认为顺序很重要，但我假设您不重要，因此3+3+1+1+1+1与3+1+3+1+1+1代表相同的解决方案。

那么，如何摆脱重复呢？一种解决方案是对每个候选向量进行排序，然后删除严格的重复项。现在我真的很懒，使用字符串字典：

var CurrentCandidate := FirstCandidate;
while GetNextCandidate(CurrentCandidate) do
  OutputCandidateVector(CurrentCandidate);

这产生

5+5
5+4+1
5+3+2
4+4+2
4+3+3
5+3+1+1
4+4+1+1
5+2+2+1
4+3+2+1
3+3+3+1
4+2+2+2
3+3+2+2
5+2+1+1+1
4+3+1+1+1
4+2+2+1+1
3+3+2+1+1
3+2+2+2+1
2+2+2+2+2
5+1+1+1+1+1
4+2+1+1+1+1
3+3+1+1+1+1
3+2+2+1+1+1
2+2+2+2+1+1
4+1+1+1+1+1+1
3+2+1+1+1+1+1
2+2+2+1+1+1+1
3+1+1+1+1+1+1+1
2+2+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1

两三秒后，尽管这种方法效率很低！

这突出了两个一般规则：

  • 给定一个明确指定的问题，通常很容易创建一个正确的算法来解决它。然而，创建一个有效的算法需要更多的工作。

  • 现在的计算机真的很快。

附录 A：完整的源代码

  • Also, let my reiterate the fact that this answer is mostly educational, displaying the very simplest way to find the result using brute-force. It's very slow, but requires almost no pre-implementation analysis; you barely need to think at all. If you compare this with some of the other answers, you'll see that they require more initial analysis (like determining individual bounds 10, 5, 3, 2, 2) and hard-coding these and offer a bit more room for source-code typos (which can be very hard to find!), but in return are *much* faster. So my main point is "Given a well-specified problem ..." above.
以上是获取给定数字的所有可能组合以达到给定的总和的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>