Create an int array of int arrays that contains all possible sums that add up to a given number

Question

I'm completely new in Java. I am writing an Android game, and I need to generate an array of int arrays that contains all possible sums (excluding combinations that contains number 2 or is bigger than 8 numbers) that add up to a given number.

For example: ganeratePatterns(5) must return array

 [patternNumber][summandNumber] = value
 [0][0] = 5
 [1][0] = 1
 [1][1] = 1
 [1][2] = 1
 [1][3] = 1
 [1][4] = 1
 [2][0] = 3
 [2][1] = 1
 [2][2] = 1
 [3][0] = 4
 [3][1] = 1

I already try to do this like there Getting all possible sums that add up to a given number but it's very difficult to me to make it like this http://introcs.cs.princeton.edu/java/23recursion/Partition.java.html

Solution

int n = 10; 
int dimension = 0; 
//First we need to count number of posible combinations to create a 2dimensionarray
for(List<Integer> sumt : new SumIterator(n)) {
 if(!sumt.contains(2) && sumt.size() < 9) {
 dimension++;
 }
}
int[][] combinationPattern = new int[dimension][];
int foo = 0;
for(List<Integer> sum : new SumIterator(n)) {
 if(!sum.contains(2) && sum.size() < 9) {
 System.out.println(sum);
 combinationPattern[foo] = toIntArray(sum);
 foo++;
 }
}

It's work not 100% correctly, and very pretty, but it is enough for my game

I have used SumIterator class from here SumIterator.class I have to changed this code for(int j = n-1; j > n/2; j--) { to this for(int j = n-1; j >= n/2; j--) { because old version doesn't return all combinations (like [5,5] for 10)

And I used toIntArray function. I have founded hare on StackOverflow, but forget a link so here it's source:

public static int[] toIntArray(final Collection<Integer> data){
 int[] result;
 // null result for null input
 if(data == null){
 result = null;
 // empty array for empty collection
 } else if(data.isEmpty()){
 result = new int[0];
 } else{
 final Collection<Integer> effective;
 // if data contains null make defensive copy
 // and remove null values
 if(data.contains(null)){
 effective = new ArrayList<Integer>(data);
 while(effective.remove(null)){}
 // otherwise use original collection
 }else{
 effective = data;
 }
 result = new int[effective.size()];
 int offset = 0;
 // store values
 for(final Integer i : effective){
 result[offset++] = i.intValue();
 }
 }
 return result;
}

• DPM: In which you find it difficult, if I may ask? It seems that instead of printing you have to update your array.
• akuzmitski: Because I'm new in Java recursion is rocket science for me:) And I can't count number off all posible patterns,to initialize an array (int[?][] = value)
• bezmax: Sorry but my head almost exploded when I tried to understand the algorithm you need to implement. Could you rephrase it's definition? Edit: Nevermind, finally got my head around it.

Answer 1

This is not the most beautiful code, but it does what you would like, having modified the code you referenced. It is also quite fast. It could be made faster by staying away from recursion (using a stack), and completely avoiding String-to-integer conversion. I may come back and edit those changes in. Running on my pretty outdated laptop, it printed the partitions of 50 (all 204226 of them) in under 5 seconds.

When partition(N) exits in this code, partitions will hold the partitions of N.

1. First, it builds an ArrayList of string representations of the sums in space-delimited format (example: " 1 1 1").

2. It then creates a two-dimensional array of ints which can hold all of the results.

3. It splits each String in the ArrayList into an array of Strings which each contain only a single number.
4. For each String, it creates an array of ints by parsing each number into an array.
5. This int array is then added to the two-dimensional array of ints.

Let me know if you have any questions!

 import java.util.ArrayList;
 public class Partition
 {
 static ArrayList<String> list = new ArrayList<String>();
 static int[][] partitions;
 public static void partition(int n)
 {
 partition(n, n, "");
 partitions = new int[list.size()][0];
 for (int i = 0; i < list.size(); i++)
 {
 String s = list.get(i);
 String[] stringAsArray = s.trim().split(" ");
 int[] intArray = new int[stringAsArray.length];
 for (int j = 0; j < stringAsArray.length; j++)
 {
 intArray[j] = Integer.parseInt(stringAsArray[j]);
 }
 partitions[i] = intArray;
 }
 }
 public static void partition(int n, int max, String prefix)
 {
 if(prefix.trim().split(" ").length > 8 || (prefix + " ").contains(" 2 "))
 {
 return;
 }
 if (n == 0)
 {
 list.add(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 = 50;
 partition(N);
 /**
 * Demonstrates that the above code works as intended.
 */
 for (int i = 0; i < partitions.length; i++)
 {
 int[] currentArray = partitions[i];
 for (int j = 0; j < currentArray.length; j++)
 {
 System.out.print(currentArray[j] + " ");
 }
 System.out.println();
 }
 }
 }

• akuzmitski: Thank you Zeychin! When I was editing my question to post my solution, you have post your own solution :). Your code works fine and pretty fast, and it's 100% correct. And it's more beautifull than mine code...
• Zéychin: Oops! It's not 100% correct. I did not exclude combinations which contain the number 2 or combinations with greater than 8 numbers! I will edit this in.
• Zéychin: I've fixed the error. Now it runs much faster, as most of the running time was in I/O.