获得所有可能的总和，加起来给定的数字
我正在为android制作一个数学应用程序。 在其中一个字段中，用户可以输入int（无数字且高于0）。 我的想法是获得所有可能的和，使得这个int，没有双打（在这种情况下4 + 1 == 1 + 4）。 唯一知道的是这一个int。
例如：
假设用户输入4，我希望应用程序返回：
- 4
- 3 + 1
- 2 + 2
- 2 + 1 + 1
- 1 + 1 + 1 + 1
显然4 == 4所以也应该加上。 关于我应该如何做这个的任何建议？
这是一个简单的算法，声称这样做
来自： 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(ni, i, prefix + " " + i); } } public static void main(String[] args) { int N = Integer.parseInt(args[0]); partition(N); } }
有一些简短而优雅的递归解决方案来生成它们，但以下内容可能更容易使用并在现有代码中实现：
import java.util.*; public class SumIterator implements Iterator>, Iterable> { // keeps track of all sums that have been generated already private Set> generated; // holds all sums that haven't been returned by `next()` private Stack> sums; public SumIterator(int n) { // first a sanity check... if(n < 1) { throw new RuntimeException("'n' must be >= 1"); } generated = new HashSet>(); sums = new Stack>(); // create and add the "last" sum of size `n`: [1, 1, 1, ... , 1] List last = new ArrayList (); 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 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> iterator() { return this; } @Override public List next() { List 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 copy = new ArrayList (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, nj); // insert `nj` 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(); } }
你可以像这样使用它：
int n = 10; for(List sum : new SumIterator(n)) { System.out.println(n + " = " + sum); }
哪个会打印：
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]
这是称为分区的数学概念。 一般来说，这很难……但是有一些技术可以用于小数字。 从维基页面链接的大量有用的东西。
对于数字N，您知道最大术语数是N.因此，您将首先列举所有这些可能性。
对于每个可能的术语数量，有许多可能性。 这个公式现在没有我，但基本上，这个想法是从（N + 1-i + 1 + … + 1）开始，其中i是术语数，并且从左到右移动1，第二种情况是be（Ni + 2 + … + 1）直到你不能做出另一个动作而不会导致未排序的组合。
（另外，你为什么再次标记这个机器人？）
这与子集和问题算法有关。
N = {N * 1，（N-1）+1，（N-2）+ 2，（N-3）+ 3 ..，N-1 = {（N-1），（（N-1） -1）+ 2，（（N-1）-1）+3 ..}
等等
所以这是一个涉及替换的递归函数; 然而，在处理大数字时是否有意义是你必须自己决定的事情。
所有这些解决方案似乎都有点复杂。 这可以通过简单地“递增”初始化为包含1 = N的列表来实现。
如果人们不介意从c ++转换，则以下算法会生成所需的输出。
bool next(vector& 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 & 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 counts(N, 1); do { print_list(counts); } while(next(counts)); return 0; }
对于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]