java 获得加起来等于给定数字的所有可能的总和

Getting all possible sums that add up to a given number

提问by Manuel

I'm making an math app for the android. In one of these fields the user can enter an int (no digits and above 0). The idea is to get all possible sums that make this int, without doubles (4+1 == 1+4 in this case). The only thing known is this one int.

我正在为 android 制作一个数学应用程序。在这些字段之一中，用户可以输入一个整数（无数字且大于 0）。这个想法是获得所有可能的和，使这个整数，没有双打（在这种情况下是 4+1 == 1+4）。唯一知道的是这个int。

For example:

例如：

Say the user enters 4, I would like the app to return:

假设用户输入 4，我希望应用程序返回：

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

• 4
• 3+1
• 2+2
• 2+1+1
• 1+1+1+1

Obviously 4 == 4 so that should be added too. Any suggestions as to how i should go about doing this?

显然 4 == 4 所以也应该添加。关于我应该如何去做的任何建议？

回答by Ashkan Aryan

Here's a simple algorithm that purports to do that

这是一个简单的算法，旨在做到这一点

from : http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html

来自：http: //introcs.cs.princeton.edu/java/23recursion/Partition.java.html

public class Partition { 

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}

public class Partition { 

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) { 
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}

回答by Bart Kiers

There are short and elegant recursive solution to generate them, but the following may be easier to use and implement in existing code:

有简短而优雅的递归解决方案来生成它们，但以下可能更易于在现有代码中使用和实现：

import java.util.*;

public class SumIterator implements Iterator<List<Integer>>, Iterable<List<Integer>> {

  // keeps track of all sums that have been generated already
  private Set<List<Integer>> generated;

  // holds all sums that haven't been returned by `next()`
  private Stack<List<Integer>> sums;

  public SumIterator(int n) {

    // first a sanity check...
    if(n < 1) {
      throw new RuntimeException("'n' must be >= 1");
    }

    generated = new HashSet<List<Integer>>();
    sums = new Stack<List<Integer>>();

    // create and add the "last" sum of size `n`: [1, 1, 1, ... , 1]
    List<Integer> last = new ArrayList<Integer>();
    for(int i = 0; i < n; i++) {
      last.add(1);
    }
    add(last);

    // add the first sum of size 1: [n]
    add(Arrays.asList(n));
  }

  private void add(List<Integer> sum) {
    if(generated.add(sum)) {
      // only push the sum on the stack if it hasn't been generated before
      sums.push(sum);
    }
  }

  @Override
  public boolean hasNext() {
    return !sums.isEmpty();
  }

  @Override
  public Iterator<List<Integer>> iterator() {
    return this;
  }

  @Override
  public List<Integer> next() {
    List<Integer> sum = sums.pop();                         // get the next sum from the stack
    for(int i = sum.size() - 1; i >= 0; i--) {              // loop from right to left
      int n = sum.get(i);                                   //   get the i-th number
      if(n > 1) {                                           //   if the i-th number is more than 1
        for(int j = n-1; j > n/2; j--) {                    //     if the i-th number is 10, loop from 9 to 5
          List<Integer> copy = new ArrayList<Integer>(sum); //       create a copy of the current sum
          copy.remove(i);                                   //       remove the i-th number
          copy.add(i, j);                                   //       insert `j` where the i-th number was
          copy.add(i + 1, n-j);                             //       insert `n-j` next to `j`
          add(copy);                                        //       add this new sum to the stack
        }                                                   //     
        break;                                              //   stop looping any further
      }                                                     
    }
    return sum;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

You can use it like this:

你可以这样使用它：

int n = 10;
for(List<Integer> sum : new SumIterator(n)) {
  System.out.println(n + " = " + sum);
}

which would print:

这将打印：

10 = [10]
10 = [6, 4]
10 = [6, 3, 1]
10 = [6, 2, 1, 1]
10 = [7, 3]
10 = [7, 2, 1]
10 = [8, 2]
10 = [9, 1]
10 = [5, 4, 1]
10 = [5, 3, 1, 1]
10 = [5, 2, 1, 1, 1]
10 = [8, 1, 1]
10 = [7, 1, 1, 1]
10 = [4, 3, 1, 1, 1]
10 = [4, 2, 1, 1, 1, 1]
10 = [6, 1, 1, 1, 1]
10 = [5, 1, 1, 1, 1, 1]
10 = [3, 2, 1, 1, 1, 1, 1]
10 = [4, 1, 1, 1, 1, 1, 1]
10 = [3, 1, 1, 1, 1, 1, 1, 1]
10 = [2, 1, 1, 1, 1, 1, 1, 1, 1]
10 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

回答by AakashM

This is the mathematical concept known as partitions. In general, it's... difficult, but there are techniques for small numbers. A load of useful stuff linked from the wiki page.

这是称为分区的数学概念。一般来说，这很……困难，但有适用于小数字的技巧。从维基页面链接的大量有用的东西。

回答by njzk2

For a number N you know that the max number of terms is N. so, you will start by enumerating all those possibilities.

对于数字 N，您知道术语的最大数量为 N。因此，您将从枚举所有这些可能性开始。

For each possible number of terms, there are a number of possibilities. The formula eludes me now, but basically, the idea is to start by (N+1-i + 1 + ... + 1) where i is the number of terms, and to move 1s from left to right, second case would be (N-i + 2 + ... + 1) until you cannot do another move without resulting in an unsorted combination.

对于每个可能的项数，都有多种可能性。这个公式现在让我无法理解，但基本上，这个想法是从 (N+1-i + 1 + ... + 1) 开始，其中 i 是项的数量，然后从左到右移动 1，第二种情况是是 (Ni + 2 + ... + 1) 直到你不能做另一个动作而不导致未排序的组合。

(Also, why did you tagged this android again?)

（另外，你为什么再次标记这个机器人？）

回答by mcfinnigan

This is related to the subset sum problemalgorithm.

这与子集求和问题算法有关。

N = {N*1, (N-1)+1, (N-2)+2, (N-3)+3 .., N-1 = {(N-1), ((N-1)-1)+2, ((N-1)-1)+3..}

N = {N*1, (N-1)+1, (N-2)+2, (N-3)+3 .., N-1 = {(N-1), ((N-1) -1)+2, ((N-1)-1)+3..}

etc.

等等。

So it's a recursive function involving substitution; whether that makes sense or not when dealing with large numbers, however, is something you'll have to decide for yourself.

所以它是一个涉及替换的递归函数；然而，在处理大量数字时这是否有意义，则必须由您自己决定。

回答by ceorron

All of these solutions seem a little complex. This can be achieved by simply "incrementing" a list initialized to contain 1's=N.

所有这些解决方案似乎都有点复杂。这可以通过简单地“递增”初始化为包含 1's=N 的列表来实现。

If people don't mind converting from c++, the following algorithm produces the needed output.

如果人们不介意从 C++ 转换，则以下算法会生成所需的输出。

bool next(vector<unsigned>& counts) {
    if(counts.size() == 1)
        return false;

    //increment one before the back
    ++counts[counts.size() - 2];

    //spread the back into all ones
    if(counts.back() == 1)
        counts.pop_back();
    else {
        //reset this to 1's
        unsigned ones = counts.back() - 1;
        counts.pop_back();
        counts.resize(counts.size() + ones, 1);
    }
    return true;
}

void print_list(vector<unsigned>& list) {
    cout << "[";
    for(unsigned i = 0; i < list.size(); ++i) {
        cout << list[i];
        if(i < list.size() - 1)
            cout << ", ";
    }
    cout << "]\n";
}

int main() {
    unsigned N = 5;
    vector<unsigned> counts(N, 1);
    do {
        print_list(counts);
    } while(next(counts));
    return 0;
}

for N=5 the algorithm gives the following

对于 N=5，算法给出以下

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3]
[1, 2, 1, 1]
[1, 2, 2]
[1, 3, 1]
[1, 4]
[2, 1, 1, 1]
[2, 1, 2]
[2, 2, 1]
[2, 3]
[3, 1, 1]
[3, 2]
[4, 1]
[5]