## combinations

Discuss all kind of algorithms and data structures from their mathematical and programming sides.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard

### combinations

I am trying to make a software that has to calculate an equation of 18 lines and 30 variables. I thought to use to use gauss elimination for the solution but what if instead I try to make combinations of the values until I get the result I want?
eduard77

Posts: 6
Joined: Mon Dec 14, 2009 9:12 am

### Re: combinations

By "calculate" an equation you mean solve it? One equation and 30 variables usually is not enough to determine a unique solution. Gaussian elimination only makes sense if what you have is a system of linear equations...

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA

### Re: combinations

I have an equation like this
87a+ 87b+ 87c+ 88d+ 90e+ 88f+ 88g+ 93h+ 92i+ 98j+ 94k = 8515
9a+ 12b+ 11c+ 15d+ 27e+ 46f+ 34g+ 50h+ 64i+ 27.1j+ 35k = 1598
8a+ 10.45b+ 91. 1c+ 12.1d+ 21.76e+ 39.42f+ 30.19g+ 39h+ 39i+ 56.83j = 1400
4a+ 2b+ 2c+ 4d+ 8e+ 15f+ 1.5g+ 10h+ 9i = 279
1.5a+ 1.5b+ 2.5c+ 5.5d+ 4.5e+ 6f+ 30 g+ 15.5h = 173
33.8a+ 30.8b+ 27.1c+ 14.5d+ 23.48e+ 22.3f+ 13g+ 23.5h+ 29.4i+ 88j+ 18.44k = 2965.41
2a+ 2b+ 5c+ 10.5d+ 8.5e+ 5f+ 23g+ 4h+ = 470
0.26a+ 0.34b+ 0.41c+ 0.63d+ 0.6e+ 2.89f+ 1.21g+ 2.42h+ 5.05i+ 0.95j = 67
0.2a+ 0.28b+ 0.33c+ 0.46d+ 0.36e+ 2.56f+ 1.05g+ 1.9h+ 4.32i+ = 57
0.19a+ 0.19b+ 0.18c+ 0.23d+ 0.6e+ 0.63f+ 0.79g+ 0.58h+ 1.82i+ 2.66j = 31
0.17a+ 0.17b+ 0.15c+ 0.19d+ 0.48e+ 0.57f+ 0.73g+ 0.49h+ 1.64i+ = 27
0.19a+ 0.28b+ 0.24c+ 0.32d+ 0.4e+ 0.67f+ 0.6g+ 0.58h+ 1.57i+ = 29
0.15a+ 0.25b+ 0.2c+ 0.23d+ 0.25e+ 0.55f+ 0.53g+ 0.36h+ 0.45i+ = 0.25
a+b+c+d+e+f+h+g+i+j+k=99
all the numbers have to be positive

=
eduard77

Posts: 6
Joined: Mon Dec 14, 2009 9:12 am

### Re: combinations

Usually we call each line an "equation". What you have is a "system of linear equations". Since you also have some restrictions that look like linear inequalities ("all the numbers have to be positive"), you have yourself a linear programming problem. Linear programming problems typically involve some objective function that has to be minimized or maximized. If you just want to find a solution, but don't care which one, you only have to use the part of the solver that finds an admissible solution, which is typically the first step in a linear-programming algorithm.

EDIT: In some sense you can think of this problem as finding a convex hull described as an intersection of hyperspaces. Chapter 15 of this book seems to deal precisely with this problem.

Alvaro
Moderator

Posts: 5185
Joined: Mon Sep 22, 2003 4:57 pm
Location: NY, USA