Expand roots into a polynomial

MATL, 29 bytes

ljU"1@_hX+]tn:Pqv'+%gx^%g'wYD

Input is an array with the roots.

EDITS:

  • (May 20, 2016): the X+ function has been removed, as Y+ includes its functionality. So in the above code replace X+ by Y+.
  • (September 29, 2017): due to changes in the YD function, w in the above code should be removed.

The following link includes those changes.

Try it online!

Explanation

This applies repeated convolution with terms of the form [1, -r] where r is a root.

l          % push number 1
jU         % take input string. Convert to number array
"          % for each root r
  1        %   push number 1
  @_       %   push -r
  h        %   concatenate horizontally
  X+       %   convolve. This gradually builds array of coefficients
]          % end for each
tn:Pq      % produce array [n-1,n-2,...,0], where n is the number of roots
v          % concatenate vertically with array of coefficients
'+%gx^%g'  % format string, sprintf-style
w          % swap
YD         % sprintf. Implicitly display

Jelly, 15 bytes

Æṛ‘Ė’Uj€“x^”j”+

This uses Æṛ to construct the coefficients of a monic polynomial with given roots. Try it online!

How it works

Æṛ‘Ė’Uj€“x^”j”+  Main link. Argument: A (list of roots)

Æṛ               Yield the coefficients of a monic polynomial with roots A.
  ‘              Increment each root by 1.
   Ė             Enumerate the roots, yielding
                 [[1, coeff. of x^0 + 1], ... [n + 1, coeff. of x^n + 1]].
    ’            Decrement all involved integers, yielding
                 [[0, coeff. of x^0], ... [n, coeff. of x^n]].
     U           Upend to yield [[coeff. of x^0, 0], ... [coeff. of x^n, n]].
      j€“x^”     Join each pair, separating by 'x^'.
            j”+  Join the pairs, separating by '+'.

Alternate version, 24 bytes

1WW;ð0;_×µ/‘Ė’Uj€“x^”j”+

This uses no polynomial-related built-ins. Try it online!

How it works

1WW;ð0;_×µ/‘Ė’Uj€“x^”j”+  Main link. Argument: A (list of roots)

1WW                       Yield [[1]].
   ;                      Concatenate with A.
    ð    µ/               Reduce [[1]] + A by the following, dyadic chain:
     0;                     Prepend a zero to the left argument (initially [1]).
                            This multiplies the left argument by "x".
        ×                   Take the product of both, unaltered arguments.
                            This multiplies the left argument by "r", where r is
                            the root specified in the right argument.
      _                     Subtract.
                            This computes the left argument multiplied by "x-r".
           ‘Ė’Uj€“x^”j”+  As before.

Ruby, 155 bytes

Anonymous function, input is an array of the roots.

Prints from lowest power first, so calling f[[1,2]] (assuming you assigned the function to f) returns the string "2x^0+-3x^1+1x^2".

->x{j=-1
x.map{|r|[-r,1]}.reduce{|a,b|q=a.map{|c|b=[0]+b
b.map{|e|e*c}[1..-1]}
q.pop.zip(*q).map{|e|(e-[p]).reduce(:+)}}.map{|e|"#{e}x^#{j+=1}"}.join('+')}

Tags:

Code Golf