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, asY+
includes its functionality. So in the above code replaceX+
byY+
. - (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('+')}