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

Question

我有 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...

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

Answer 1

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

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

11 × Lowest allowed summand = 11 × 1 = 11

这已经大于 10。

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

11 × Lowest allowed summand = 11 × 1 = 11

但是请注意，两个不同的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

由于每个被加数是从一组基数 6 中选择的，因此有 6 ¹⁰ = 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)。

让我们试试这个枚举：

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

（实现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
...

现在我们“完成”了：

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：完整的源代码

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
...

Answer 2

另一种方法是转换为线性方程，其中 A、B、C、D 和 E 是 1、2、3、4 或 5 的数量。

A + B*2 + C*3 + D*4 + E*5 = 10

确定每个变量的范围。

A = (0..10)   // can be 0 to 10 1's
B = (0..5)    // can be 0 to 5 2's
C = (0..3)    // etc
D = (0..2)
E = (0..2)

尝试所有组合。要检查的组合总数：11 * 6 * 4 * 3 * 3 = 2,376。

  for var A : integer := 0 to 10 do
    for var B : integer := 0 to 5 do
      for var C : integer := 0 to 3 do
        for var D : integer := 0 to 2 do
          for var E : integer := 0 to 2 do
            if A * 1 + B * 2 + C * 3 + D * 4 + E * 5 = 10 then
            begin
              // output a solution
            end;

完整的源解决方​​案

program Project1;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.StrUtils;

begin
  for var A : integer := 0 to 10 do
    for var B : integer := 0 to 5 do
      for var C : integer := 0 to 3 do
        for var D : integer := 0 to 2 do
          for var E : integer := 0 to 2 do
            if A * 1 + B * 2 + C * 3 + D * 4 + E * 5 = 10 then
            begin
              Var AResult : string := '';
              for Var I :integer := 1 to E do AResult := AResult + ' + 5';
              for Var I :integer := 1 to D do AResult := AResult + ' + 4';
              for Var I :integer := 1 to C do AResult := AResult + ' + 3';
              for Var I :integer := 1 to B do AResult := AResult + ' + 2';
              for Var I :integer := 1 to A do AResult := AResult + ' + 1';
              writeln(RightStr( AResult,length(AResult) -3) + ' = 10');
            end;
  readln;
end.