Integer partition into sums and products

Question

Here is what I need to do: write an algorithm that will split a given integer into sums and products but each following number must be bigger than the previous one, i.e:

6 = 1+5;
6 = 1+2+3;
6 = 1*2+4;
6 = 2+4;
6 = 2*3;

A basic partition integer algo is not going to work since it returns numbers in a different order.

I'm not asking for a final code, I'm just asking for some tips and advices so I can move on myself. Thank you so much in advance!

Answer 1

public class Perms {

/**
 * @param args
 */
public static int x;
public static void main(String[] args) {
    // TODO Auto-generated method stub

    x = 6;
    rec(x, new int[1000], new String[1000], 0);
}

public static void rec(int n, int all[], String operator[], int size)
{
       if (n==0)
       {
          if (size==1)return;
          System.out.print(x + " =");
          for (int i=0;i<size;i++)
          {
             System.out.print(" " + all[i]);
             if (i!=size-1)
                 System.out.print(" " + operator[i]);
          }
          System.out.println();
          return;
       }
       int i=1;
       if (size>0)
          i = all[size-1]+1;
       for ( ;i<=n;i++)
       {
          operator[size] = "+";
          all[size] = i;
          rec(n-i, all, operator, size+1);
       }

       i=1;
       if (size>0)
          i = all[size-1]+1;
       for (;i<=n;i++)
       {
          float r = n/(float)i;
          if (r == (int)r)
          {
             operator[size] = "*";
             all[size] = i;
             rec(n/i, all, operator, size+1);
          }
       }
    }
}

Output:

6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
6 = 1 * 2 + 4
6 = 1 * 6
6 = 1 * 2 * 3
6 = 2 * 3

Note: Operations have post priorities(Evaluate operations from right to left).

Example: 20 = 2 * 3 + 7 = (2 * (3 + 7)) = 2 * 10 = 20.

It's easy to add those parentheses. but, output will look ugly. Just noting that is better.

Answer 2

Here's what I came with, which is a very inefficient brute force method. It printed this out:

6 = 1 * 2 * 3
6 = 1 + 2 + 3
6 = 2 * 3
6 = 1 * 2 + 4
6 = 2 + 4
6 = 1 + 5
6 = 1 * 6

Source:

package com.sandbox;

import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class Sandbox {

    public static void main(String[] args) {
        int n = 6;

        List<List<Integer>> numberPermutations = Permutations.getPermutations(n);
        for (Iterator<List<Integer>> iterator = numberPermutations.iterator(); iterator.hasNext(); ) {
            List<Integer> permutation = iterator.next();
            if (permutation.size() <= 1) {
                iterator.remove();  //remove x = x
            }
        }

        Set<List<Character>> symbolPermutations = Permutations.getSymbols(n); //outputs (+), (*), (++), (+*), (*+), (**), ...

        for (List<Integer> numberPermutation : numberPermutations) {
            for (List<Character> symbolPermutation : symbolPermutations) {
                if (numberPermutation.size() - 1 == symbolPermutation.size()) {    //eg: if you've got 1, 2, 3, 4, 5, 6 as numbers, then you want the symbols between them like +, *, *, *, +.  Notice there's one less symbol than the numbers
                    int sum = numberPermutation.get(0);
                    String equation = sum + "";
                    for (int i = 1; i < numberPermutation.size(); i++) {
                        Integer thisInt = numberPermutation.get(i);
                        if (symbolPermutation.get(i - 1) == '+') {
                            sum += thisInt;
                            equation += " + " + thisInt;
                        } else {
                            sum *= thisInt;
                            equation += " * " + thisInt;
                        }
                    }
                    if (sum == n) {
                        System.out.println(sum + " = " + equation);
                    }
                }
            }
        }
    }

}

I'll leave getting the permutations up to the reader.

Answer 3

Here's an idea:

Using dynamic programming, you can store all the valid ways of writing a number. Then, to calculate the valid ways of writing a larger number, use the results from before. Would work well recursively.

Say valid(x) is the function to compute all the valid ways of writing x. Recursively:

valid(x) =
1 if x == 1
Or the entire collection of:
For i = 1 to x/2
valid(i) + (x-i)
And
For i = all divisors of x <= sqrt(x)
valid(x) * x/i

I don't think you can calculate much more efficiently than that. Also, be sure to memorize (store in memory) the progressive calculations of valid(x).

EDIT: Forgot about the case of 7 = 1 + 2 * 3 and others like it. Looks like the above answer works better.

Answer 4

Well I was writing code for someone else with similar (not same) question and he erased before I post it :).

So I have a code for you, which do similar thing and you should be able to change it to whatever you want.

This code shows all possibilities of sum with given number of terms, for example for number 7 and number of terms 4, it prints this result :

7 = 4+1+1+1
7 = 3+2+1+1
7 = 2+3+1+1
7 = 1+4+1+1
7 = 3+1+2+1
7 = 2+2+2+1
7 = 1+3+2+1
7 = 2+1+3+1
7 = 1+2+3+1
7 = 1+1+4+1
7 = 3+1+1+2
7 = 2+2+1+2
7 = 1+3+1+2
7 = 2+1+2+2
7 = 1+2+2+2
7 = 1+1+3+2
7 = 2+1+1+3
7 = 1+2+1+3
7 = 1+1+2+3
7 = 1+1+1+4

I hope it should not be difficult to use the idea of this and change it to what you need.

public class JavaApplication25 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int terms = 4;
        int sum = 7;
        int[] array = new int[terms];
        for (int i = 0; i < terms; i++) {
            array[i] = 1;
        }
        boolean end = false;
        int total = 0;
        while (end == false){
            if (sumAr(array) == sum){
                print(array,sum);
                total++;
            }
            end = increase(array, sum);
        }
        System.out.println("Total numbers: " + total);
    }

    public static void print(int[] array, int sum){
        System.out.print(sum + " = ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i != array.length-1){
                System.out.print("+");
            }
        }
        System.out.println("");
    }

    public static boolean increase(int[] array, int max){
        for (int i = 0; i < array.length; i++) {
            if (array[i] != max){
                array[i]++;
                for (int j = i-1; j >= 0; j--) {
                    array[j]=1;
                }
                return false;
            }
        }
        return true;
    }

    public static int sumAr(int[] array){
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        return sum;
    }
}

Tip : If you dont care about effectivness, you can just run this code for all possible terms (for number 7 it can be 1-7 terms) and add some if-statement, which discards values, you dont want (that the next number must be higher than previous)