Partial Fractions

Question

Given an input of a string, output the partial fraction in string form.

The partial fraction decomposition of a rational fraction of the form \$\frac{f(x)}{g(x)}\$, where \$f\$ and \$g\$ are polynomials, is its expression as:

$$\frac{f(x)}{g(x)}=p(x)+\sum_j\frac{f_j(x)}{g_j(x)}$$

In this case \$p\$ is 0, because we assume that the numerator is smaller than the denominator.

Input:

In the form of an a list of the coefficients:

[[1, 4], [[1,3], [1,3]]]

For (x+4)/(x+3)^2.

Output:

In the form of a list too:

[[[1], [1, 3]], [[1], [1, 6, 9]]]

For 1/(x+3) + 1/(x+3)^2.

Assumptions

• The power of - x^ can be of any power greater than 1
• The fractions are factorised whenever possible
• You can output the elements of a list or the list itself
• You can take the input as a list or separate elements
• The numerator highest degree is always lower than the denominator highest degree
• You can take the input and output in any order
• The input will not be in a way such that the numerator and denominator have a factor in common
• You can assume all inputs take this form: $$\frac{something}{(something)(something)(...)}$$
• Note there can be multiple fractions e.g.: $$\frac{x+4}{(x+1)(x-2)(x+3)^2}$$

Note:

This is not as easy as it looks This only gets harder. There are multiple cases to follow:

1. Linear factors

$$\frac{N(x)}{(ax+b)(cx+d)}=\frac{A}{ax+b}+\frac{B}{cx+d}$$

2. Repeated linear factors

$$\frac{N(x)}{(ax+b)^2}=\frac{A}{ax+b}+\frac{B}{(ax+b)^2}$$

3. Quadratic factor (non-factorisable)

$$\frac{N(x)}{(ax+b)(x^2+bx+c)}=\frac{A}{ax+b}+\frac{Bx+C}{x^2+bx+c}$$

Testcases

Case 1:
[1,4], [[1,3], [1,2]] -> [[-1], [1,3]], [[2], [1,2]]

$$\frac{x+4}{(x+3)(x+2)}=\frac{-1}{x+3}+\frac{2}{x+2}$$

Case 2:
[1,4], [[1,3], [1,3]] -> [[1], [1,3]], [[1], [[1,3], [1,3]]]

$$\frac{x+4}{(x+3)^2}=\frac{1}{x+3}+\frac{1}{(x+3)^2}$$

Case 3:
[2,-1,4], [[1,0], [1,0,4]] -> [[1], [1,0]], [[1,-1], [1,0,4]]

$$\frac{2x^2-x+4}{x(x^2+4)}=\frac{1}{x}+\frac{x-1}{x^2+4}$$

Answer 1

Python3, 1029 bytes:

import itertools as I
E=enumerate
U=lambda x:{len(x)-i:a for i,a in E(x,1)}
def G(v,r=[]):
 if[]==v:yield r;return
 for k in I.product(*[[-1,0,1]for _ in v[0]]):
  N=[a+b for a,b in zip(v[0],k)]
  if N[0]:yield from G(v[1:],r+[N])
  else:yield from G(v[1:],r+[[-1]+N[1:]])
def P(p):
 if[]==p:return{0:1}
 s=U(p[0])
 for e in p[1:]:
  n={}
  for i,a in E(e,1):
   for A in s:n[A+len(e)-i]=n.get(A+len(e)-i,0)+s[A]*a
  s=n
 return s
T=lambda x:P([eval(i)for j,k in x for i in[j]*k])
H=lambda n,N:[1]+[0]*(max(n)-max(N))
def f(n,d):
 S,D,M={*map(str,d)},[],{}
 for i in S:Y=d.count(eval(i));D+=[(i,Y)]+[(i,1)]*(Y>1 and len(S)==1);M[i]=max(Y,M.get(i,0))
 N=U(n);q,O=[[(a,b,t:=T([(j,M[j])for j in{*M}-{a}]+[(a,M[a]-b)]*(M[a]-b>0)),H(N,t))for a,b in D]],[]
 while q:
  a=q.pop(0)
  O+=[a]
  r={}
  for *_,p,o in a:
   for A,B in P([[*p.values()],o]).items():r[A]=r.get(A,0)+B
  if r==N:return[[i[-1],[eval(i[0])]*int(i[1])]for i in a]
  for i in G([j[-1]for j in a]):
   v=[(A,B,C,z)for (A,B,C,_),z in zip(a,i)]
   if v not in O:q+=[v]

Try it online!

Answer 2

Mathematica, 124 bytes

#~CoefficientList~x&/@{Numerator@#,Denominator@#}&/@List@@Apart[First@#~FromDigits~x/Fold[Times,(#~FromDigits~x&)/@Last@#]]&

View it on Wolfram Cloud!

Apart does the heavy lifting here. The rest of the code allows it to work on the specified input and output format.