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

Improve this question
\$\endgroup\$
8
  • 7
    \$\begingroup\$ "It's not as easy as it looks" Well, it doesn't look particularly easy :P \$\endgroup\$ Commented 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\$ Commented Oct 11, 2022 at 15:32
  • 3
    \$\begingroup\$ I feel like mathematica has a built in for this.... \$\endgroup\$ Commented 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\$ Commented Oct 11, 2022 at 16:22
  • 6
    \$\begingroup\$ @Pacmanboss256 I guess reference.wolfram.com/language/ref/Apart.html? \$\endgroup\$ Commented Oct 11, 2022 at 16:27

2 Answers 2

Reset to default
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!

Improve this answer
\$\endgroup\$
9
  • 1
    \$\begingroup\$ there's whitespace in the second to last line: for (A,B,C...) \$\endgroup\$ Commented Oct 11, 2022 at 18:43
  • \$\begingroup\$ suggest O+=[a:=q.pop(0)] \$\endgroup\$ Commented Oct 11, 2022 at 18:49
  • \$\begingroup\$ also from itertools import* saves a byte \$\endgroup\$ Commented 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\$ Commented 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\$ Commented 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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @DialFrost I felt it was justified seeing as ~96% of the answer is for I/O ;) \$\endgroup\$ Commented Oct 12, 2022 at 4:21

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.