Java: Creating an Ordered Polynomial

Question

Given a polynomial, for example, 5x^4 - 1x^2 +2x^2 -3 +5x I create the following three arrays whose indexes match up with the variable,degree, and coefficient that each "item" in the polynomial has.

coefficentArray=[5, -3, 2, -1, 5]
variableArray = [x,  , x, x, x]
degreeArray   = [1, 1, 2, 2, 4]  //sorted on

I am attempting to write code that adds up all of the "items" with the same degrees and same variable, and returns a String of the new polynomial, so for instance what I'm looking for here would be +5x^4 +1x^2 +5x^1 -3x^0. Here is my function so far...

    public static String putItTogether(int[] array,int[] array1, String[] array2, int count)
{
    int j = count; //count is number of items in arrays
    StringBuilder builder = new StringBuilder();
    for (int i=count; i<=0 ; i--) {
         int answer = 0;
         while (array[j] == array[j-1]) {   //array = degrees //array1 = coefficients // array2 = variable
              if (array2[j] == array2[j-1]) { //if they both have x in same index
                    answer = array1[j] + array1[j-1];//add the coefficients
              }
         j--;
         }
      String coefficientString = Integer.toString(answer); //create string from answer
      String degreeString = Integer.toString(array[j]); //get the degree and turn it into a String 
      if (answer < 0)
          builder.append("-") //if answer negative, add negative sign
      else
          builder.append("+") // else add positive sign

      builder.append(coefficientString); //add coefficient to builder
      builder.append("x"); //add "x" to coefficient in builder

      builder.append("^"); //add the "^" after the "x"
      builder.append(degreeString); //finally add the degree after the "^"
      buider.append(" "); //add space inbetween
      }
    }
    return builder.toString();
}

Using the polynomial given at the top as input, I'm receiving +0x^0 +0x^0.Been staring at it for a couple hours now and can't seem to find anything, so thought I'd try to get another set of eyes on it. Thanks for your time, it's truly appreciated. Also, if you think I should kill my little "code-baby" and approach the problem from a different angle don't be afraid to tell me!

Answer 1

I'd suggest killing your current plan. Doing the reduce logic and then outputting all in one loop can be very messy. Instead, you should do the reduce logic in one method, and then another method to print out the result of the reduce logic.

Now for the approach, the list of degrees and list of coefficients are great for the input and we will keep those, but you don't need the list of variables if your only variable is x. I see why you have the variable array (for constants) but remember that the constant C = C * x^0 (a constant has degree zero as x^0=1) so basically every single item in the equation has a variable of x.

Now for the first part of reducing the equation, I'd suggest using a map where the key is the degree of the variable and the value is the coefficient value. This will be used to keep track of the coefficient value for each degree.

Note, the map for the equation 3x^2 + 2x + 3 would look like

degree --> coefficient (coefficient x^degree)

2 --> 3 (3 x^2)

1 --> 2 (2 x^1)

0 --> 3 (3 x^0)

So the the reduce algorithm would look like this . . .

public TreeMap<Integer,Integer> reducePolynomial(int[] coefficients, int[] degrees) {
  TreeMap<Integer,Integer> polynomials = new TreeMap<Integer,Integer>();
  for(int i = 0; i < coefficients.length; i++) {
      int coefficient = coefficients[i];
      int degree = degrees[i];

      if(polynomials.containsKey(degree)) {
         // sum coefficients of the same degree
         int currentCoefficient = polynomials.get(degree);
         polynomials.put(degree, currentCoefficient + coefficient);
      }  else {
         // no coefficient for the current degree, add it to map
         polynomials.put(degree, coefficient);
      }
  }

  return polynomials;
}

The output of the program is the degree to coefficient map. Then you can use that map to construct your equation string. We will take each entry degree --> coefficient and turn it into +-coefficient x^degree

public String outputPolynomial(TreeMap<Integer,Integer> polynomials) {
   StringBuilder builder = new StringBuilder();
   for(Entry<Integer,Integer> polynomial : polynomials.descendingMap().entrySet()) {
     if(polynomial.getValue() != 0) {
       // append plus (note negative coefficient will print out a minus sign)
       if(polynomial.getValue() >= 0) {
           builder.append("+ "); 
       }

       // append coefficient
       builder.append(polynomial.getValue());

       builder.append("x^");

       // append degree
       builder.append(polynomial.getKey());

       builder.append(" ");
     }
   }
   return builder.toString();
} 

The idea behind all of this is to reduce your input lists into a single handy data structure, then use that data structure to output the results.

Finally, if you want to expand this algorithm to use multiple variables (y, z, ...) then you could construct multiple maps, one for each variable, plus one variable to keep track of constant values.

Edit: Addressing comments

where does the + 0x^0 come from?

That's a bug in what I wrote. I modified the code so that if the polynomial coefficient = 0, then don't output the current polynomial.

How to ouptput in descending degree order?

I implemented HashMaps which don't have an order but TreeMaps do. You could make a new TreeMap<Integer,Integer>(); then you can do something like

NavigableMap <Integer, Integer> polynomialsDesc = treeMap.descendingMap();
for(Entry<Integer,Integer> polynomial : polynomialsDesc) {
   ... output logic ...
}

I modified the code above to use a TreeMap instead.