生成所有唯一的数字组合，加起来达到一定数量 [英] Generate all of the unique combinations of numbers that add up to a certain number

问题描述

我正在编写一个程序来尝试解决数学问题。我需要生成一个唯一的列表，所有的数字，加起来另一个数字。例如，所有4个数字的组合，最多5个是：

  5 0 0 0 
 4 1 0 0 
 3 2 0 0 
 3 1 1 0 
 2 2 1 0 
 2 1 1 1 
  

这是很容易暴力的perl，但我在C工作，并希望找到一个更优雅的解决方案。

在perl中，我将在每一列中生成数字0-N的每个可能的组合，丢弃不加上目标数字的那些，然后对每行中的数字排序并删除重复的行。 p>

我一直在尝试在C写这个，但似乎没有一个令人满意的解决方案。我需要它工作到最大N约25 。你们有什么想法吗？

这是我一直在尝试的一个例子（这产生重复组合）：

  // target是每行应该和的数字。 
 //不要担心溢出，我只为目标使用小值
 void example（int target）
 {
 
 int row [4]; 
 
 for（int a = target; a> = 0; a--）{
 row [0] = a; 
 
 for（int b = target-a; b> = 0; b--）{
 row [1] = b; 
 
 for（int c = target-（a + b）; c> = 0; c--）{
 row [2] 
 
 row [3] = target-（a + b + c）; 
 
 printf（％2d％2d％2d％2d sum：％d\\\
，row [0]，row [1]，row [2]，row [3]，
 row [0] + row [1] + row [2] + row [3]）; 
} 
} 
} 
} 
  

解决方案

这被称为分区问题< a>和方法在此处，这里和此处。

I am writing a program to try to solve a math problem. I need to generate a unique list of all of the numbers that add up to another number. For example, all of the unqiue combinations of 4 numbers that add up to 5 are:

5 0 0 0
4 1 0 0 
3 2 0 0
3 1 1 0
2 2 1 0
2 1 1 1

This is easy to brute force in perl but I am working in C and would like to find a more elegant solution.

In perl I would generate every possible combination of numbers 0-N in each column, discard the ones that don't add up to the target number, then sort the numbers in each row and remove the duplicate rows.

I've been trying all morning to write this in C but can't seem to come up with a satisfactory solution. I need it to work up to a maximum N of about 25. Do you guys have any ideas?

Here is an example of the kind of thing I have been trying (this produces duplicate combinations):

// target is the number each row should sum to.
// Don't worry about overflows, I am only using small values for target
void example(int target)
{

  int row[4];

  for (int a=target; a>=0; a--) {
    row[0] = a;

    for (int b=target-a; b>=0; b--) {
      row[1] = b;

      for (int c=target-(a+b); c>=0; c--) {
        row[2] = c;

        row[3] = target-(a+b+c);

        printf ("%2d %2d %2d %2d   sum: %d\n", row[0],row[1],row[2],row[3],
                                          row[0]+row[1]+row[2]+row[3]);
      }
    }
  }
}

解决方案

This is called a partition problem and approaches are discussed here, here and here.

这篇关于生成所有唯一的数字组合，加起来达到一定数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！