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 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 3

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.