查找和为 100 的 4 个正整数的所有列表

Question

我想生成一个包含 4 个正整数的所有可能列表的列表，其总和正好等于 100。（加数不需要是唯一的。）

可能的示例片段：

[
 // Using (1+1+1+97)
 [1,1,1,97],
 [1,1,97,1],
 [1,97,1,1],
 [97,1,1,1],

 // Using (2+1+1+96)
 [2,1,1,96],
 [2,1,96,1],
 [2,96,1,1],
 [96,2,1,1],

 [1,2,1,96],
 [1,2,96,1],
 [1,96,2,1],
 [96,1,2,1],

 [1,1,2,96],
 [1,1,96,2],
 [1,96,1,2],
 [96,1,1,2],

 // Using (2+2+1+95), etc...
]

执行此操作的有效方法是什么？（伪代码或建议都可以。）

Answer 1

我认为最直接的方法是使用3个循环。

resultList = []
for a from 1 to 97:
  for b from 1 to 97:
    for c from 1 to 97:
      d = 100-a-b-c
      if d > 0:
        resultList.append([a,b,c,d])

Answer 2

我认为最好从一个解决方案开始，然后将解决方案更改为其他有效的解决方案。我认为 0 不是有效数字。

让我们从 [97,1,1,1] 开始然后我们从 97 中减去 1，剩下 96。我们有 [96,1,1,1] 离开 1。所以我们有一个问题给了我们部分答案：

"generate a list of all possible lists of 3 positive integers whose sum equals 4"

然后我们用96减一，

"generate a list of all possible lists of 3 positive integers whose sum equals 5"

然后我们用95减一，

"generate a list of all possible lists of 3 positive integers whose sum equals 6"

等等等

因为一堆问题看起来真的很像原来的问题，所以我们可以 re-do 从 3 个地方到 2 个地方。 [2,1,1](留1)=>"generate a list of all possible lists of 2 positive integers whose sum equals 3"好写。

现在你可以简单地编写一个漂亮的递归公式。

Answer 3

递归方法：

MakeSum(Sum, NItems, ResultList)
  if NItems = 1
    output ResultList + [Sum]
  else
     for i = 1 to Sum - NItems + 1
        MakeSum(Sum - i, NItems - 1, ResultList + [i])

Answer 4

这是 Python 中的一个简单解决方案，它按字典顺序生成所有可能的结果：

resultList = []
for a in xrange(1,98):
    for b in xrange(1,98):
        for c in xrange(1,98):
            d = 100 - a - b - c
            if d > 0 and a <= b <= c <= d:
                resultList.append([a,b,c,d])

结果列表有 7153 个条目，从 [1,1,1,97] 开始，到 [25,25,25,25] 结束。您可以运行位于 http://ideone.com/8m7b1h 的程序。

Answer 5

迭代和递归解决方案：（试试 DartPad

void main() {
  List<List<int>> resultList1 = <List<int>>[];
    for(int i1 = 1; i1 < 98; i1++)  {
    for(int i2 = 1; (i1 + i2) < 99; i2++) {
      for(int i3 = 1; (i1 + i2 + i3) < 100; i3++) {
        for(int i4 = 1; (i1 + i2 + i3 + i4) <= 100; i4++) {
          if((i1 + i2 + i3 +i4) == 100) {
            resultList1.add([i1, i2, i3, i4]);
          }
        }
      }
    }
  }
//  print(resultList1);
  print(resultList1.length);
  final int elementCount = 4;
  final int target = 100;
  final List<List<int>> resultList2 = <List<int>>[];
  sum(elementCount, target, resultList2, [0, 0, 0, 0], 0);
//  print(result);
  print(resultList2.length);
}

void sum(int elementCount, int target, List<List<int>> result, List<int> values,
    int curPos) {
  for (int i = values[curPos] + 1; i <= target - curPos; i++) {
    // debugging only
//    if(curPos == 0) {
//      print(i);
//    }
    // end debugging only
    values[curPos] = i;
    if (curPos == elementCount - 1) {
      if (values.reduce((int a, int b) => a + b) == 100) {
//        print(values);
        result.add(values.toList());
      }
    } else {
      sum(elementCount, target, result, values, curPos + 1);
    }

    for(int j = curPos + 1; j < values.length; j++) {
      values[j] = 0;
    }
  }
}

结果包含从[1,1,1,97]到[97,1,1,1]的156849个元素。递归版本支持可变数量的元素和可变总和目标值。例如通过这样调用它：

  final int elementCount = 3;
  final int target = 50;
  final List<List<int>> resultList2 = <List<int>>[];
  sum(elementCount, target, resultList2, [0, 0, 0], 0);

Answer 6

这是适用于任意数量零件的通用解决方案：

// create(100, 4) returns the 156849 solutions
Iterable<List<int>> create(int max, int parts) sync* {
  assert(max >= parts);
  if (parts == 1) {
    yield [max];
  } else {
    for (int i = max - parts + 1; i > 0; i--) {
      yield* create(max - i, parts - 1).map((e) => e.toList()..add(i));
    }
  }
}

以及针对 4 个数字的更优化解决方案：

// create(100) returns the 156849 solutions
Iterable<List<int>> create(int max) sync* {
  for (int a = 1; a <= max - 3; a++) { // -3 because b/c/d are >= 1
    for (int b = 1; b <= max - a; b++) {
      for (int c = 1; c <= max - a - b - 1; c++) { // -1 because d is >=1
        yield [a, b, c, max - a - b - c];
      }
    }
  }
}

查找和为 100 的 4 个正整数的所有列表

FInd all lists of 4 positive integers whose sum is 100

algorithm

combinations

sum

dart