Encuentre los coeficientes de una función generadora racional

12

Si escribimos una secuencia de números como los coeficientes de una serie de potencias, entonces esa serie de potencia se denomina función generadora (ordinaria) (o Gf) de esa secuencia. Es decir, si para alguna función F(x)y serie de enteros a(n)tenemos:

a(0) + a(1)x + a(2)x^2 + a(3)x^3 + a(4)x^4 + ... = F(x)

Entonces F(x)es la función generadora de a. Por ejemplo, la serie geométrica nos dice que:

1 + x + x^2 + x^3 + x^4 + ... = 1/(1-x)

Entonces la función generadora de 1, 1, 1, ...es 1/(1-x). Si diferenciamos ambos lados de la ecuación anterior y multiplicamos por x, obtenemos la siguiente igualdad:

x + 2x^2 + 3x^3 + 4x^4 + ... = x/(1-x)^2

Entonces la función generadora de 1, 2, 3, ...es x/(1-x)^2. Generar funciones es una herramienta muy poderosa, y puede hacer muchas cosas útiles con ellas. Aquí se puede encontrar una breve introducción , pero para una explicación realmente exhaustiva existe la sorprendente función de generación de libros.


En este desafío, tomará una función racional (el cociente de dos polinomios con coeficientes enteros) como entrada como dos conjuntos de coeficientes enteros, primero el numerador y luego el denominador. Por ejemplo, la función f(x) = x / (1 - x - x^2)se codificará como [0, 1], [1, -1, -1]en la entrada.

Dada esta entrada, su programa debe imprimir infinitamente los coeficientes de la serie de potencia que equivale a la función de generación, uno por línea, comenzando en el coeficiente de x, luego x^2, etc.


Ejemplos:

[1], [1, -1] -> 1, 1, 1, 1, 1, 1, 1, ...
[1], [2, -2] -> 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 0.5, ...
[0, 1], [1, -2, 1] -> 1, 2, 3, 4, 5, 6, 7, 8, ...
[0, 1], [1, -1, -1] -> 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
[1], [1, -2] -> 1, 2, 4, 8, 16, 32, 64, 128, ...
[0, 1, 1], [1, -3, 3, -1] -> 1, 4, 9, 16, 25, 36, ...
orlp
fuente
Mierda, mi lenguaje está diseñado para secuencias de este, pero realmente no puedo hacer una entrada de matriz multidimensional :(
Stephen
2
Realmente no tengo una mentalidad matemática suficiente para esta especificación, ¿hay alguna posibilidad de que puedas publicar más explicaciones de un laico para la gente común?
Skidsdev
2
Posible duplicado de Calcular coeficientes de la serie de potencia
trichoplax
1
@trichoplax Eso siempre obliga al numerador a ser 1, que no es lo mismo. Por ejemplo, no puede expresar mi último ejemplo, los cuadrados.
orlp
1
Una forma alternativa de redactar esto es que evalúa una recurencia lineal general. De esa manera, generaliza esta pregunta y podría servir como objetivo de engaño para futuras preguntas de recurrencia.
Peter Taylor

Respuestas:

7

Haskell , 63 bytes

z=0:z
(a:b)%y@(c:d)=a/c:zipWith(-)(b++z)(map(a/c*)d++z)%y
_%_=z

Pruébalo en línea!

Define un operador que %devuelve una lista infinita de coeficientes perezosos. La lista está indexada a cero, por lo que se incluye el coeficiente constante.

Anders Kaseorg
fuente
3

Mathematica, 64 83 90 bytes

Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}‌​]&

Gracias a @ngenisis y @Jenny_mathy!

Tome la entrada como dos listas.

Necesita Alt+.terminar la ejecución para ver el resultado. La interfaz puede bloquearse debido a la salida rápida.

Versión de 83 bytes (@Jenny_mathy):

i=1;v=Tr[#*x^Range@Length@#]&;While[1<2,Echo@Limit[D[v@#/v@#2/i!,{x,i}],x->0];i++]&
Keyu Gan
fuente
83 bytes: i = 1; v = Tr [# * x ^ Rango @ Longitud @ #] &; Mientras [1 <2, Eco @ Limit [D [v @ # / v @ # 2 / i !, {x, i}], x -> 0]; i ++] &
J42161217
@ Jenny_mathy Perdón por molestar. Me doy cuenta de que hay algunos caracteres Unicode invisibles basura en su primer comentario. Una vez limpiado, el código está bien.
Keyu Gan
3
64bytes: Do[Echo@Limit[D[#/#2/i!&@@Fold[x#+#2&]/@#,{x,i}],x->0],{i,∞}]&. Esto supone que la entrada es una lista de dos listas y los coeficientes están en orden descendente. Lo único que conozco para hacer lo que vhace esInternal`FromCoefficientList
ngenisis
¿Funciona esto repetidamente? Creo que un par de paréntesis adicionales podrían ser necesarios para poner identro de la lambda. (Por otro lado, no estoy realmente seguro de si la capacidad de correr repetidamente es relevante cuando el objetivo es imprimir una lista infinita ... ¿ha habido un meta consenso sobre esto?)
Julian Wolf
@ngenisis: ¿Qué versión estás usando? En v10.0, tu solución me da Iterator {i,∞} does not have appropriate bounds.
Julian Wolf
1

CJam (22 bytes)

{\{(W$(@\/_pW*f*.+1}g}

Demo en línea . Tenga en cuenta que, como muchas de las respuestas existentes, esto incluye el coeficiente 0 en la salida.

Disección

{           e# Define a block which takes numerator N and denominator D as arguments
  \         e# Flip to put D at the bottom, since that won't change
  {         e# Infinite loop:
    (       e#   Pop the first element of (the modified) N
    W$(     e#   Copy D and pop its first element
            e#   Stack: D N[1:] N[0] D[1:] D[0]
    @\/     e#   Bring N[0] to top, flip, divide
            e#   Stack: D N[1:] D[1:] N[0]/D[0]
    _p      e#   Print a copy
    W*f*.+  e#   Multiply by -1, multiply all, pointwise add
            e#   Stack: D N[1:]-(N[0]/D[0])*D[1:]
  1}g
}
Peter Taylor
fuente
0

Mathematica, 86 79 bytes

f=x^Range@Length@#.#&;For[n=1,8>3,Print@SeriesCoefficient[f@#/f@#2,{x,0,n++}]]&

Toma la entrada como dos listas separadas (coeficientes del numerador, coeficientes del denominador). Si la entrada puede tomarse directamente como una fracción de polinomios en lugar de como listas de coeficientes, esto puede acortarse significativamente.

Parece que Dopuede funcionar con límites infinitos en v11. No puedo probar esto localmente, pero, si este es el caso, entonces esta solución se puede acortar a 75 bytes :

f=x^Range@Length@#.#&;Do[Print@SeriesCoefficient[f@#/f@#2,{x,0,n}],{n,∞}]&
Julian Wolf
fuente
último caso de prueba no comienza con 0.
J42161217
@ Jenny_mathy: dispara, gracias por el aviso. Parece que los casos de prueba esperan comenzar desde el principio en lugar del cero ... bastante seguro de que esto debería permitirme guardar algunos bytes.
Julian Wolf
@ Jenny_mathy: Creo que los casos de prueba podrían ser inestables. A npartir de 1 en lugar de 0, esto da los mismos resultados que su solución; ambos fallan, sin embargo, en el penúltimo caso de prueba, que esta solución pasa al comenzar ndesde 0.
Julian Wolf
0

Pyth , 23 bytes

JE#
KchQhJ=t-M.t,Q*LKJ0

Pruébalo en línea!

Cómo funciona

                       Q = eval(input())
JE                     J = eval(input())
  #                    infinite loop:
 chQhJ                   Q[0]/J[0]
K                        assign that to K (and print it, because of the preceding newline)
              *LKJ       K times every element of J
            ,Q           [Q, that]
          .t      0      transpose, padding with 0s
        -M               subtract each pair
       t                 remove the first element
      =                  assign that back to Q
Anders Kaseorg
fuente