At the moment it just provides a couple of mathematical functions via a dll. My reasons for posting this program were more to protect my possible claim of an algorithm, than to give an easy to use program (I explained that in my first post). That is why I have paid extra attention on the math description of what I am doing (I write it parallel with the code).
Although the program is not useful "as is" I do hope it could, one day, help a stuck math graduate student like myself. That is why I plan to write an interface to one of the popular math programs (for example, it could be MAPLE or MAGMA).
So here's what it does: (disclaimer: some math ahead!)
My program is about solving the following problem. Say you are given a set of vectors with positive integer coordinates (mathematical vectors lol: that is a sequence of n numbers. n is called in this case "the dimension" of the "vector space"). Let those vectors be v_1,...,v_k. These vectors are concrete integer vectors: for example:
v_1=(1,0)
v_2=(0,1)
v_3=(1,1)
The dimension of the space in the example is 2.
Then you are given another vector, say w=(x_1,x_2,...,x_n), however, x_1,...,x_n are not concrete numbers, but are formal parameters. The question is:
In how many ways can you write the vector w=(x_1,...,x_n) as a non negative integer sum of the vectors v_1,...,v_k ?
In our example, let us take the vector w=(2,2). Then it can be written in 3 different ways as a non-negative integer sum of the v_1, v_2, v_3:
w= 2*v_1+2*v_2 = 2*(1,0)+2*(0,1)
w= v_1+v_2+v_3= (1,0)+(0,1)+(1,1)
w=2*v_3= 2*(1,1)
Wait a minute... I was asking my question for general values of the vector w=(x_1,..,x_n), not for concrete values of w! Cheater!
Ok, but for this simple example, you can actually solve the problem for arbitrary w=(x_1,x_2). For fun, I will write it directly in c++ :
1 2 3 4 5 6 7 8
|
int NumWays(int x_1, int x_2)
{ if (x_1<0 || x_2<0)
return 0;
if (x_1<=x_2)
return x_1+1;
else
return x_2+1;
}
|
Now I leave it up to you to reason why this is so for this concrete example. (it is very easy to see).
What do we see from this example:
1) there exist finitely many inequalities that determine different answers (in this case, two pairs of inequalities x_2 > 0, x_1 > x_2; and x_1>0, x_2>x_1)
2) if we know which of the inequalities are satisfied (and there are only finitely many), the answer is a polynomial expression with respect to x_1,...,x_n (in our concrete example, the polynomials x_1+1 and x_2+1)
Note: 2) is actually a lie; the true answer is a bit technical and involves the word "quaipolynomials", however the main idea is completely the same. The problem comes from the example: take one-dimensional vector space and let v_1 be the vector (2). Then the vector (3) cannot be written as a non-negative integer sum of copies of v_1.
So, what my program does is the following:
0) You feed it in vectors
1) It computes you the inequalities that were explained on the example
2) It computes the (quasi)polynomials that give the answer
(a screen shot of my program with what the answer looks like for a set of vectors in 3 dimensional space (the graphics represent the different "combinatorial chambers" that are determined by the inequalities):
https://sourceforge.net/project/screenshots.php?group_id=263224
)
What do I need this program for is a reaaaaaally long story, but let's just say I never wanted to write it, I just wanted to have the output for a concrete set of 15 vectors lying in 5-dimensional space. However, when I googled with the expectation of seeing 10 different programs doing this (you should google vector partition function), well... I found a bunch of articles and a program that could only compute the number (actually a little bit more, I don't want to go in details), but not at all the algebraic expression that I presented in the above example (the program is called Latte).
So this is how I came about to meet the world of C++ :)