Construct a polynomial with given roots

Question

The challenge is to write the shortest function/program to find a polynomial given the roots. The function or program should take valid input; that is, a list of integers representing the roots of the polynomial, and return valid output.

Output should return a sequence of numbers representing the polynomial. For example:

2, 3 represents 2x^1 - 3x^0 = 0

1, 6, 1, 8, 0, 3, 3 represents 1x^6 + 6x^5 + 1x^4 + 8x^3 + 0x^2 + 3x^1 + 3x^0 = 0

-1 0 5, -3 represents -1x^3 + 0x^2 + 5x^1 + -3x^0 = 0

I hope you get the idea.

Example Usage

For an input of 1, 2, the output should be 1, -3, 2, which represents the equation 1x^2 + -3x^1 + 2x^0 = 0, or x^2 - 3x + 2 = 0.

For an input of 1, -1, 0, the output should be 1, 0, -1, 0.

For the input, duplicate values should be removed and order does not matter. For example, the result with input 3, 3, 6 should be the same as the result with input 6, 3.

Float arguments are optional.

As this is code golf, the shortest entry in characters wins. Good luck!

Answer 1

J, 8 bytes

A series of verbs:

|.p.1;~.

Call it like this:

   |.p.1;~. 1 2
1 _3 2

J has a built-in verb p. (Roots). It converts between polynomials like 2 _3 1 (reverse order from the problem) and a multiplier/root pair like (1; 1 2).

From right-to-left, ~. takes the unique elements, 1; pairs the list with 1, meaning we want the smallest integer polynomial, p. does the actual work, and |. reverses the resulting list.

Answer 2

Python 2, 71

P=[1]
for r in set(input()):P=map(lambda a,b:a-r*b,P+[0],[0]+P)
print P

Iteratively updates the polynomial P to add one root at a time. Adding the root r multiplies the polynomial as P*(x-r). This requires shifting the polynomial list P by one index to represent multiplication by x, the subtracting r times the original list. This is handled by shifting a copy of the list, padding with zeroes, and mapping the function a,b -> a-r*b.

To remove duplicate roots, the input is made into a set.

Using reduce turned out one char longer (72):

lambda R:reduce(lambda P,r:map(lambda a,b:a-r*b,P+[0],[0]+P),set(R),[1])

Three lambdas though!

Answer 3

Haskell, 70

Basically a port of the reduce version of my Python solution.

import Data.List
foldr(\x p->zipWith(\a b->a-b*x)(p++[0])(0:p))[1].nub

I tried to shorten the lambda expression \a b->a-b*x by making it point-free, but best I have is (+).(*(-x)) on switched inputs (thanks to @isaacg), which is the same length.

The lengthy import for nub is for the requirement to ignore duplicate roots. Without it, we'd have 49:

foldr(\x p->zipWith(\a b->a-b*x)(p++[0])(0:p))[1]

Answer 4

Matlab, 56 bytes

Polynomial multiplication is convolution of their coefficients:

function y=f(R)
y=1;for r=unique(R);y=conv(y,[1 -r]);end

Floating-point roots are supported.

Example:

>> f([1 2])
ans =
     1    -3     2
>> f([1 2 1])
ans =
     1    -3     2
>> f([1 2.1 -3.2])
ans =
    1.0000    0.1000   -7.8200    6.7200

Answer 5

Ruby 2.7+, 60 58 57 50 bytes

->i{p=*1;(i&i).map{|x|p<<z=0;p.map!{-x*z+z=_1}};p}

Requires ruby 2.7+ for numbered arguments to work. Based on xnor's python answer

Takes input as an array of roots, and returns an array of coefficients.

Thanks to @Martin Ender for -2 bytes!

Thanks to Lydxn for -1 byte

Thanks to JoKing for -7 bytes.

Answer 6

Julia, 41 bytes

Note: this is assuming the list is what matters, not the input/output format.

s->foldl((i,j)->[0,i]j+[i,0],1,unique(s))

Answer 7

Pyth, 17 bytes

u-V+G0*LH+0GS{Q]1

17 bytes. A reduce over the input set. +G0 is essentially *x, and *LH+0G is essentially *r, and -V performs element by element subtraction to perform *(x-r).

Demonstration.

Answer 8

Jelly, 3 bytes

QÆṛ

Try it online!

Outputs them in order from the zero coefficient first. +1 byte to go the other way

It would just be a builtin (Æṛ) aside from the fact that duplicates shouldn't matter. Therefore we deduplicate the input first with Q, then use the builtin

Answer 9

CJam, 24 21 bytes

1al~_&{W*1$f*0\+.+}/`

Input format is a list in square brackets (e.g. [1 2]). Output format is the same. This is a full program. It might get slightly shorter if I package it as an anonymous function.

The approach is fairly straightforward: It starts out with 1 for the polynom, which is described by a coefficient array of [1]. It then multiplies it with x - a for each root a. This results in two arrays of coefficients:

• One from the multiplication with -a, which simply multiplies each previous coefficient by this value.
• One from the multiplication with x, which shifts the array of coefficients by 1, padding the open position with 0.

The two are then combined with a vector addition. I actually don't have to do anything for the second array, since CJam uses remaining array elements of the longer array unchanged if the other array is shorter, so padding the second array with a 0 is redundant.

Try it online

Explanation:

1a      Put starting coefficient array [1] on stack.
l~      Get and interpret input.
_&      Uniquify input array, using setwise and with itself.
{       Loop over roots given in input.
  W*      Negate value.
  1$      Get a copy of current coefficient array to top.
  f*      Multiply all values with root.
  0\+     Add a leading zero to align it for vector addition.
  .+      Vector add for the two coefficient array.
}/      End loop over roots.
`       Convert array to string for output.

Answer 10

Javascript, 121 bytes

r=>{o=[...r,0].fill(0);for(i=2**r.length;i--;)e=r.length,a=r.reduce((a,q,j)=>a*(i&1<<j?q:(e--,-1)),1),o[e]+=a;return o;}

Explantation

Similar to other answers, we imagine a polynomial of the form:

 (r_1 - x) * (r_2 - x) * ... * (r_n - x)

And we want to multiply it out to get the polynomial:

 a_0 * x^n + ... + a_n * x^0

This program does that by looping over every permutation of the input brackets. We can do this by counting in binary from 0 to 2^n. The i-th bit of that count tells us whether to multiply by r_i, or by -x.

Ungolfed:

function make_poly(roots) {
  o = [...roots, 0].fill(0);
  for (i = 0; i < 2 ** roots.length; i++) {
    a = 1;
    t_index = roots.length;
    for (j = 0; j < roots.length; j++) {
      if (i & (1 << j)) {
        a *= roots[j];
      } else {
        a *= -1;
        t_index--;
      }
    }
    o[t_index] += a;
  }
  return o;
}

Answer 11

Husk, 13 bytes

FȯmΣ∂Ṫ*moe1_u

Try it online!

Explanation

The idea is to generate the polynomials (x-r0),…,(x-rN) for the roots r0,…,rN and simply multiply them out:

F(mΣ∂Ṫ*)m(e1_)u  -- accepts a list of roots, example: [-1,1,-1]
              u  -- remove duplicates: [-1,1]
        m(   )   -- map the following (eg. on 1):
            _    --   negate: -1
          e1     --   create list together with 1: [1,-1]
F(     )         -- fold the following function (which does polynomial multiplication),
                 -- one step with [1,-1] and [1,1]:
     Ṫ*          --   compute outer product: [[1,1],[-1,-1]]
    ∂            --   diagonals: [[1],[1,-1],[-1]]
  mΣ             --   map sum: [1,0,1]