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;
}

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();
            }
        }
    }