6
\$\begingroup\$

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}$$

  1. Repeated linear factors

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

  1. 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}$$

\$\endgroup\$
8
  • 7
    \$\begingroup\$ "It's not as easy as it looks" Well, it doesn't look particularly easy :P \$\endgroup\$ Oct 11, 2022 at 14:14
  • 1
    \$\begingroup\$ Are we to assume that the "somethings" in the denominator are no more than second order? Ie. will the denominator always be [L1, L2, ...] where Ln is no more than 3 elements? \$\endgroup\$ Oct 11, 2022 at 15:32
  • 3
    \$\begingroup\$ I feel like mathematica has a built in for this.... \$\endgroup\$
    – pacman256
    Oct 11, 2022 at 16:20
  • 1
    \$\begingroup\$ Could you provide a clearer explanation of the requirements, at the moment it just has a formula with four undefined terms (\$p\$, \$j\$, \$f_j\$, and \$g_j\$) - apart from the test cases I don't see what stops \$p\$ being the input with the sum being zero. What should the denominators (\$g_j\$?) of the terms in the output be? What is \$p\$ and what can we use it for? \$\endgroup\$ Oct 11, 2022 at 16:22
  • 6
    \$\begingroup\$ @Pacmanboss256 I guess reference.wolfram.com/language/ref/Apart.html? \$\endgroup\$ Oct 11, 2022 at 16:27

2 Answers 2

8
\$\begingroup\$

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!

\$\endgroup\$
8
  • 1
    \$\begingroup\$ there's whitespace in the second to last line: for (A,B,C...) \$\endgroup\$
    – c--
    Oct 11, 2022 at 18:43
  • \$\begingroup\$ suggest O+=[a:=q.pop(0)] \$\endgroup\$
    – c--
    Oct 11, 2022 at 18:49
  • \$\begingroup\$ also from itertools import* saves a byte \$\endgroup\$
    – c--
    Oct 11, 2022 at 19:08
  • \$\begingroup\$ yield from G(*N[0]and(v[1:],r+[N])or(v[1:],r+[[-1]+N[1:]])) also works \$\endgroup\$
    – c--
    Oct 11, 2022 at 19:19
  • \$\begingroup\$ and for A in s:j=A+len(e)-i;n[j]=n.get(j,0)+s[A]*a \$\endgroup\$
    – c--
    Oct 11, 2022 at 19:53
4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Hey... you cheated! :3 (nah its fine) \$\endgroup\$
    – DialFrost
    Oct 12, 2022 at 4:18
  • \$\begingroup\$ @DialFrost I felt it was justified seeing as ~96% of the answer is for I/O ;) \$\endgroup\$
    – hakr14
    Oct 12, 2022 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.