I would like to expand polynomial from form like this : (x - x1) (x-x2) (x-x3) ... while I have x1,x2,x3... in form of array, to polynomial form like a x^3 + b x^2 + c , where arguments are in array.
For the logic of this, see what the expansions look like on Wolfram alpha (e.g. expand (x-a)(x-b)(x-c)(x-d)(x-e)).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main
{
public static void main(String[] args)
{
// (x-5)(x-4)(x-3)(x-2)(x-7)
int[] xs = { 5, 4, 3, 2, 7 };
List<Integer> coefficients = new ArrayList<>();
boolean positive = true;
for (int i = 0; i < xs.length + 1; ++i) {
int coefficient = 0;
if (i > 0) {
List<int[]> combos = combos(xs, i);
for (int[] nums : combos) {
int product = 1;
for (int num : nums) {
product *= num;
}
coefficient += product;
}
} else {
coefficient = 1;
}
coefficients.add(coefficient * (positive ? 1 : -1));
positive = !positive;
}
for (int i = 0; i < coefficients.size(); ++i) {
int coefficient = coefficients.get(i);
int exponenent = (coefficients.size() - i - 1);
System.out.print(coefficient + "*x^" + exponenent + (exponenent == 0 ? "" : " + "));
}
}
// Combinations of xs size k
private static List<int[]> combos(int[] xs, int k)
{
List<int[]> result = new ArrayList<>();
for (ArrayList<Integer> comboIdxs : combine(xs.length, k)) {
int[] combo = new int[comboIdxs.size()];
for (int i = 0; i < comboIdxs.size(); ++i) {
combo[i] = xs[comboIdxs.get(i)];
}
result.add(combo);
}
return result;
}
// Thanks http://www.programcreek.com/2014/03/leetcode-combinations-java/
public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (n <= 0 || n < k)
return result;
ArrayList<Integer> item = new ArrayList<Integer>();
dfs(n, k, 0, item, result); // because it need to begin from 1
return result;
}
private static void dfs(int n, int k, int start, ArrayList<Integer> item,
ArrayList<ArrayList<Integer>> res) {
if (item.size() == k) {
res.add(new ArrayList<Integer>(item));
return;
}
for (int i = start; i < n; i++) {
item.add(i);
dfs(n, k, i + 1, item, res);
item.remove(item.size() - 1);
}
}
}