Receiving all possible amounts up to a certain number

Question

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

For instance:

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

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

Obviously 4 == 4, and this should also be added. Any suggestions on how I should do this?

Answer 1

Here is a simple algorithm that tries to do this

from: 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); } } 

Answer 2

There is a short and elegant recursive solution for creating 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, 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(); } } 

You can use it as follows:

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

which will 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, 1]

Answer 3

This is a mathematical concept known as sections . All in all, it's ... complicated, but there are methods for small numbers. Download useful material related to the wiki page.

Answer 4

For the number N, you know that the maximum number of members is N. Therefore, you will start by listing all of these possibilities.

For each possible number of terms, there are a number of possibilities. The formula eludes me now, but in principle the idea is to start with (N + 1-i + 1 + ... + 1), where I am the number of members, and to move 1s from left to right, the second case be (Ni + 2 + ... + 1) until you can make another move without leading to an unsorted combination.

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

Answer 5

This is due to the subset sum algorithm . .

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, this is a recursive function involving substitution; regardless of whether it makes sense or not when dealing with large numbers, you must decide for yourself.

Answer 6

All of these solutions seem a bit complicated. This can be achieved simply by "incrementing" the list initialized to contain 1 = N.

If people do not mind converting from C ++, the following algorithm produces the necessary output.

 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

 [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]