3

I am looking for a module or a function to write that does the following in Python:

Say I have two matrices:

left = ['2B', '1A', '2A+1B']
right = ['8C', '3C', '2D']

I want to find the smallest whole numbers for A, B, C, and D (all must be greater than 0) such that 

left = right

So, in this case, we have:

2*B = 8*C
A = 3*C
2*A + B = 2*D

Therefore, 

A = 3
B = 4
C = 1
D = 5

My matrices are formatted as shown above - they are lists of strings with each capital letter needed to be solved for.

The matrices can be arbitrary size, I just chose length 3 as an example.

Any ideas? Thanks!

EDIT: Someone in the comments made a good point. I guess there is a possibility that there are two solutions, one with A being "smallest" and another with B being "smallest". But in my case, I am using this as a chemical equation balancer, so as far as I know this can never happen - there should always be one correct, smallest solution.

Joe
  • 116
  • 1
  • 16
  • How do you determine "smallest"? A system could easily have two solutions where one has a smaller A and the other has a smaller B. – user2357112 Jun 08 '16 at 18:05
  • 2
    Related and Highly off topic post [Simplest way to solve mathematical equations in Python](http://stackoverflow.com/q/1642357) – Bhargav Rao Jun 08 '16 at 18:08
  • 1
    take a look here: http://docs.sympy.org/dev/modules/solvers/solvers.html. you have to figure how write your equations in matrix form and apply solver – dot.Py Jun 08 '16 at 18:14
  • this might also help: https://www.youtube.com/watch?v=44pAWI7v5Zk – dot.Py Jun 08 '16 at 18:14
  • @Dot_Py Thanks for the video and link. But I don't really know how to use that in this way. Those are solving definite equations - finding x in Ax = b - but I have more of Ax = By and I need to solve for both x and y. – Joe Jun 08 '16 at 18:21
  • you can rewrite your system to ax =b form... but you have 4 variables and 3 equations... how you managed to solve that? – dot.Py Jun 08 '16 at 18:33

1 Answers1

3

In general, you are trying to solve a system of equations over the integers, which is no simple task (check out this paper).

However there are some tools that can help, assuming you put in the work to transform your lhs, rhs lists into a matrix representing your system.

The fantastic SymPy package is a good place to start, they have a set of solvers which allow you to specify the system along with external constraints (like being a positive integer).

Note that in your example, you have four unknowns and three equations, meaning that your solution will have at least one free variable, which will add some complexity to your overall solution.

evan.oman
  • 5,922
  • 22
  • 43