A (complex) question on numbers

Hi Folks,

I am a college undergrad (microbiology...not cs) in the middle of a research project. There are 3 sets of numbers I am looking at, and I want to run a rather complex analysis of them. I took a couple years of C++ in high school, so I am under the impression that a program can be coded to do what I want done, but alas, I don't know enough C++ to do it. Does anyone have thoughts on how to code this?...

I have 3 sets of numbers:
x (1, 2, 3, 4, 5, 6, 7...)
y (21, 22, 23, 24, 25, 26...)
z (14, 15, 16, 17, 18...)

I want to determine if any average of any of the numbers in sets x and y equals (or is very close to) one of the numbers in z. The trick is, the average could be 1 number from each set, 2 numbers from 1 set and 1 number from the other, etc. When averaging 2 or more numbers from each set, the numbers dont have to be consequtive. So I pretty much want to test every possibility. Tough, huh? It doesn't have to be pretty or fast, just work ;). Anyone know how to do this? THanks so much for your time.

[email protected], or just reply

that's an interesting problem. i'm a little rusty with my combinatorics (hopefully someone can verify) but first off that's a whole lotta possibilites. if 'i' was the number of elements in set-x, and 'j' the number of elements in set 'y'. then all possible combinations of elements from x and y to combine in some calculation for an average would be:

2^i * 2^j

thus for i = j = 10, that's 1048576 individual calculations of averages, not to mention that many comparisons with elements in z. i speculate that with any i and j > 15-20, you will be sitting in front of your computer for quite some time... lol. anyways, this problem is interesting and i'll try and implement a program when i get the chance.

Yes, that *is* a lot of possibilities. In fact, the 2 number sets consist of 17 numbers, and the target set has 15. I wonder how long it would take a nice fast P4 to calculate that?

Thanks for your help! Let me know if there is anything I can answer to help.
[email protected]

I think you forgot to include that fact that at least one number must be set 'on' from each set. Why else would you want to sepearate the sets then? Otherwise you could just make one large set composed of both sets ( w/o repeats eliminated ).

Like this:
possible from set a = 2^i - 1 because it cant have all zeros and similarly,
b = 2^j - 1

multiply those two possible combinations together and you get:
2^(i+j) - 2^i - 2^j + 1

so for i = j = 10; thats really 1046529. (not much a difference, huh?). But this would be important if you wanted to display some sort of progess indicator.

You could probably save some time by not dividing the sum of numbers everytime.

For example:
rather than do [ abs(target - (a + b + c)/3) <= threshold ]
do [ abs(3 * target - (a+b+c)) <= threshold * 3 ]

Doesn't seem to save much time right? Well, keep in mind that the other two numbers are constants. If you made an array of pre-multiplied targets and thresholds, you could rewrite it as this:

abs(target[3] - (a+b+c)) <= threshold[3]

This saves multiplication. It also increases accuracy because if your dealing with integers, (a+b+c)/3 could lead to round-off errors.

Example:
threshold = 2
target = 3
a+b+c = 17

abs(3 - (17)/3) <= 2
abs(3 - 5) <= 2
2 <= 2; true!

abs(3*3 - 17) <= 2*3
abs(9 - 17) <= 6
8 <= 6; false!

Interesting program. I'll look into it. And if I don't, this might help someone else get a start.

Quote:

---

I think you forgot to include that fact that at least one number must be set 'on' from each set. Why else would you want to sepearate the sets then? Otherwise you could just make one large set composed of both sets ( w/o repeats eliminated ).

---

good point.

I did that because the 2 number sets are from 2 different places. There is no reason, however, why they can't be combined.

Thanks!
[email protected]

But must there be at least one number from each set? Your original post suggests this may be the case.

I did that because the 2 number sets are from 2 different places. There is no reason, however, why they can't be combined.

Thanks!
[email protected]

No, it is not necessary that at least one number between each set. However, if it is easier to code so that at least one number is from each set, that is fine. Thanks again,
[email protected]