Find the generating function of a sequence [duplicate]

Question

Given a set of space-delimited integers, you've gotta either return a function that can generate that sequence, or return "There isn't any such function".

Sample input:

"1 11 41 79"
 - x^3+x^2-1

"12 38 78"
 - 7x^2 + 5x

The operations that the functions can contain are: +-/* and exponentiation.

If anyone has any other ideas LMK. As this is a code-golf, the shortest code will win.

Answer 1

Python 256 bytes

a=raw_input().split();r=range(len(a));m=[[(i+1.)**p for p in r]+[int(a[i])]for i in r]
for j in r:s=m[j];m=[map(lambda a,b:a-b*(i[j]-(i==s))/s[j],i,s)for i in m]
while~j:
 c=m[j][-1]
 if c:print('%+.15g'%c)[s>c>0:j>=c*c==1or 18]+('x^%d'%j)[:j*j],;s=0
 j-=1

Sets up a system of linear equations, matrix style, and then uses Gaussian elimination to solve. Quite a few bytes are spent pretty-printing the output. Non-integer solutions are displayed to 15 digits of accuracy.

As every sequence of n real numbers can be generated by a polynomial of order no more than n-1, the "function does not exist" case is not handled.

Sample usage:

$ echo 1 11 41 79 | python find-poly.py
-2x^3 +22x^2 -42x +23

$ echo 1 11 35 79 | python find-poly.py
x^3 +x^2 -1

$ echo 12 38 78 | python find-poly.py
7x^2 +5x

$ echo 43 12 -5 19 57 | python find-poly.py
-2.25x^4 +27x^3 -98.75x^2 +110x +7

Answer 2

There was no restriction in using any specific library, so here is a solution in Python using Sympy

Python 2.x: 71 Characters

from sympy import*
print interpolate(map(int,raw_input().split()),abc.x)