Help me figure out the algorithm to solve a maths problem

February 14, 2011 7:01 AM

Need help from Math and IT geeks :-) Long question inside.

I'm trying to implement a program to compute the following.

inputs to the program values P, U and L. Then I create a 3D matrix PxPx(U-L+1)
For the sake of clarity lets assume P=2, U=1, L=-1
I need all the different combinations of 4 items alone Z axis.
In this instance the different combinations are as follows. (In each iteration I feed these 4 values to another function for calculations. Here for simplicity I potrait it as just addition)
matrix is as follows coeff[x][y][z]

t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][1]

//-------------
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][1]
//-------------
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][-1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][1]
//======================
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][1]

//-------------
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][1]
//-------------
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][0] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][1]
//========================
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][-1] + coeff[1][0][1] + coeff[1][1][1]

//-------------
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][0] + coeff[1][0][1] + coeff[1][1][1]
//-------------
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][-1] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][0] + coeff[1][1][1]

t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][-1]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][0]
t = coeff[0][0][1] + coeff[0][1][1] + coeff[1][0][1] + coeff[1][1][1]

I'm trying to do this in C++, but only need help in figuring out the algorithm. So even if your answer is not in C++ that's fine.

for (int k1=-1;k1<=1;k1++){
for (int k2=-1;k2<=1;k2++){
for (int k3=-1;k3<=1;k3++){
for (int k4=-1;k4<=1;k4++){
cout << "x[0][0]["<<k1<<"] \t";
cout << "x[0][1]["<<k2<<"] \t";
cout << "x[1][0]["<<k3<<"] \t";
cout << "x[1][1]["<<k4<<"]\n";
}
}
}
}

Above is a piece of code (mefi messed up my indentations) I wrote assuming all the values are constants. SO most of the things are hard coded. But my program needs to accept P, U and L as inputs and create the output on the fly.

posted by WizKid to Computers & Internet (20 answers total)

Maybe I'm not sufficiently geeky enough, but I don't understand this sentence:

I need all the different combinations of 4 items alone Z axis.
posted by bluefly at 7:12 AM on February 14, 2011

I believe he means 'along' the z-axis - the z-axis going from L (lower) to U (upper). I'm still not sure what the question is, though.
posted by nightwood at 7:22 AM on February 14, 2011

The question title says he needs help coming up with an algorithm to solve the math problem he's presenting above.
posted by killdevil at 8:32 AM on February 14, 2011

The poster may want to provide a Pastebin link to an indented version of the stuff he's listed above, if MeFi bowdlerized the formatting.
posted by killdevil at 8:35 AM on February 14, 2011

The indentation is not the problem, for me at least. He just has four deep nested for loops.

It is not clear, to me, what he means to do. Maybe you could explain what you are trying to do in the algorithm in more detail. And what the issue is? For example does the bit of the code work but you just need to know how to accept the inputs? If not, how does it fail?
posted by d4nj450n at 8:45 AM on February 14, 2011

WizKid, can you clarify what the Z axis is? You talk about the 4 values along an (undefined) Z axis, but in your example, the matrix is size 2x2x3, so there are not 4 values along any "axis" that I can imagine.

Can you maybe start over and try to explain the problem conceptually using words instead of disconnected pieces of code?
posted by fritley at 8:48 AM on February 14, 2011

I think the op is saying he can only compute this by hard-coding all of the permutations he wants, but needs to be able to do it without knowing the values of P, L, and U beforehand.

The question is a little confusing, but if I have (partially at least) understood the question then perhaps this will get you partway there:

define a list of all possible triple indices. This can be done in a loop, so you don't need to hard-code this matrix.
index=
{
{0,0,-1},
{0,0,0},
...
{1,1,0},
{1,1,1}
}

This list has length L.

define a function that gives you the coefficient you want, based off of this index
f[i]:=coeff[index[i][0]][index[i][1]][index[i][2]]

define a loop that computes your terms. In your case, it looks like you know that there are four terms in each sum, so you can use four loops:


for(i=0;i<L;i++){
for(j=0;j<L;j++){
for(k=0;k<L;k++){
for(l=0;l<L;l++){

t=f[i]+f[j]+f[k]+f[l];
//do whatever you want with t

}
}
}
}

I'm sure there are better ways to do what you want, but is this along the lines of your original question?
posted by bessel functions seem unnecessarily complicated at 9:03 AM on February 14, 2011 [1 favorite]

Well....This like that you wrote:
Then I create a 3D matrix PxPx(U-L+1)

doesn't make any sense to me. See, a 3D Matrix will be more like Px(P,U,L). What you have there tells me its a 1D matrix that is of size U-L+1. So, lets assume that you want a 3D matrix that is of size P,U,L and that U-L+1 is some sort of formula to access a certain array value OR that P,U,L are VALUES to be placed INTO the array.

Now then, your example cout's show three possible indexes, -1,0,1. This is a problem. WHY!? C++ uses a zero based array system. C++ will happily let you access a -1 index, BUT...that portion of memory actually holds the x array information .. and writing to that memory will mess things up seriously!

So, each index allocation must be >0. So if P>0, U>0 and L>0 then you are golden. Ah, but you say that U, L and U-L+1 is NOT greater than zero, each one is -1,0,1. And that is one way to look at it. BUT, another way to look at it is that there are three different values, therefore three different indexes. That is the answer. Allocation then would be AT LEAST:
int x[2][2][2];

which creates a zero based, three item array per dimension: 0,1,2. You can create x[3][3][3] and do a one based array (first value is x[1]) if you like. It wastes a little stack space but that isn't ususally a problem.

Now then, the two approaches are: PUL are array INDEXES, or PUL are array VALUES. If they are indexes, then you need to make sure they are >=0. If I know they start at -1, then I have to add 1 to index the array properly. For example:
x[P+1][U+1][L+1] = value;
This makes it so that if P=-1, then it is stored in index 0 and if P=1 then it is stored in index 2. Same goes for U and L.

HOWEVER, if P=-1 is a VALUE, then you don't worry about the index:
int i1 = 0; int i2=0; int i3=0;
x[i1][i2][i3]=P;

x will happily STORE negative values.

Now then, your brute force calculations also don't seem to make sense:
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][-1];
Beyond the fact that an index of -1 is a no-no (as previously discussed) you are overwriting t every time with a new value on each line. t looks to me to be a 'stand alone' int value and when you set it (using =) you destroy the previous value. Is this done in programming, SURE, but usually the value is USED before destroying it. so something like:
t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][-1];
cout <> t = coeff[0][0][-1] + coeff[0][1][-1] + coeff[1][0][-1] + coeff[1][1][0];
cout <>
makes more sense.

At the end, you seem to want to loop through all the array values. OK, that can be done but it must be something like this:

for (int k1=0;k1<> for (int k2=0;k2<> for (int k3=0;k3<> cout <> }
}
}

This line:
cout <> will print something like:
'x[0][0][1] '
but not the value.

So, if this doesn't make sense, please clarify the question.
posted by CodeMonkey at 9:11 AM on February 14, 2011 [1 favorite]

Hmmm, the last bit didn't paste right. Lets try again:
for (int k1=0;k1<> for (int k2=0;k2<> for (int k3=0;k3<> cout <> }
}
}
posted by CodeMonkey at 9:14 AM on February 14, 2011

AUGH: k, read up on posting code. Try this:
1.for (int k1=0;k1<=2;k1++){
2.for (int k2=0;k2<=2;k2++){
3.for (int k3=0;k3<=2;k3++){
4.cout << "x["<<k1<<"]["<<k2<<"]["<<k3<<"] \t"<<x[k1][k2][k3]<<endl;
5.}
6.}
7.}
posted by CodeMonkey at 9:15 AM on February 14, 2011

and,
This line:

1.cout <>
will print something like:
'x[0][0][1] '
but not the value.
posted by CodeMonkey at 9:23 AM on February 14, 2011

I give up.
posted by CodeMonkey at 9:23 AM on February 14, 2011 [1 favorite]

Response by poster: Thanks for all the replies. I'll add some points to clarify.

1. All the cout statements are dummy codes. In the real program instead of counts I'll pass the values of four locations to a function.

2. Array is PxPx(U-L+1) = 2x2x(1--1+1) = 2x2x3

3. Let me explain the 3d matrix I have
when z=-1
a b
c d

z=0
e f
g h

z=1
i j
k l

So I want all possible combinations of P*P (which is 4 in this example) out of the total values (which is 12 in this example).
example set 1 - abcd
example set 2 - abch
example set 1 - abcl

More than one item alone the same z line not permitted
so there can't be combinations of 4 as follows
invalid example 1 - abce (because both a and e are in the same line alone z axis)
invalid example 1 - abfd (because both b and f are in the same line alone z axis)

hope I clarified things enough :-)
posted by WizKid at 11:00 AM on February 14, 2011

So I want all possible combinations of P*P (which is 4 in this example) out of the total values (which is 12 in this example).

This doesn't follow. Are you excluding combinations such as a-f-g-l on purpose, or accidentally? If you intend to include those, there are 81 combinations (3^4), not 12.
posted by fritley at 11:51 AM on February 14, 2011

Response by poster: a-f-g-l is a valid combination. I just gave few examples.
Yes, In this scenario I should get a total of 81 sets of 4 locations.
posted by WizKid at 11:56 AM on February 14, 2011

Best answer: OK, then the four nested loops (that some have tried to post, with varying success) is the obvious iterative answer, but only if P=2. If you want to support varying P, have you considered using a recursive algorithm? Notice how your example could have been written

a b c d
e f g h
i j k l

i.e. you really have a 2d problem, not a 3d problem. If you recurse by column, you end up with a base case

d
h
l

to which the answer is of course

d
h
l

At the next level up, you will take each of d h l and prepend c, then prepend g to each, then k to each:

c d
c h
c l
g d
g h
g l
k d
k h
k l

Notice I have 3^2 answers now; In two more levels you'll have your 81 answers.
posted by fritley at 12:21 PM on February 14, 2011

Response by poster: @fritley
I think you got it :-)
Thanks for the answer.

I'll give it a try. if you can give me a start with the algorithm that would be great
posted by WizKid at 12:44 PM on February 14, 2011

Well I think that is a pretty full description of the algorithm I wanted to explain... Do you have a question about it?
posted by fritley at 12:55 PM on February 14, 2011

Best answer: Here's some code. Rewrite sample_function() to do whatever you need done. As written it does what your starting example does, both by printing out the operation and by actually doing the additions.

Run with command line arguments: P L U ( just the numbers: ./main.exe 2 -1 1 )

Get the whole project if you have git installed with this command:

git clone git://github.com/dc25/ask_mefi_loop.git
posted by metadave at 1:06 PM on February 14, 2011

Response by poster: @fritley
Thanks. I'll look at it and let you know if I have any questions

@metadave
Thanks for the code. I'll give it a try
posted by WizKid at 1:23 PM on February 14, 2011