r/askmath•
notdelet

Simple question: find all middle means

Probability

Let's say I have a set of numbers of size divisible by 3. Consider all of the ways to split the numbers into 3 equally sized subsets. I am interested in enumerating (including multiplicity) all of the values of the "middle mean" of the 3 subset means. Is there a fast way to do this? Particularly when the numbers are integers and therefore the multiplicity of a given mean may be high... (flair = probability because this question comes from an application in that area)

Posted Sep 15, 2021, 2:02 AM UTC

14
notdeletOP•

So far I am somewhat stuck, as the brute force solution obviously does not ignore a lot of redundancy that should be ignored. Obviously sorting the numbers is a good 1st step. Then I was considering applying some kind of dynamic programming where I take the set of sets from the previous step, add 3 new items at a time, and update them. This way I can memoize using only the values and not the full identities of the sets, saving duplicate computation.

1
arty_dent•

When you say "mean", are you talking about the arithmetic mean or some other mean?

And when you say "middle mean" are you simply referring to the mean of the three means (both being the kind of mean you were using in the first place), or something else (maybe the median)?

In case you are only talking about arithmetic means then the whole splitting into three parts doesn't matter at all. The arithmetic mean of the arithmetic means of the three parts is always the same as the arithmetic mean of the whole.

If you meant something else then it becomes more complicated. And then it also depends on how you handle multpilicities when it comes to "all ways to split".

1
notdeletOP•

Arithmetic mean, but other non-median means would probably cause the same problem as well. The middle mean is as it sounds - the median of the three.

1
arty_dent•

Hm...not sure what a good algorithm would be. That might depend a lot on whether you know something about the inout data, i.e., the list of numbers.

Generally, the worst case (without further restrictions on the input data) can't be handled significantly faster than by brute force, simply because there might not be any redundancy: given a list of 3N numbers - there could be up to at least nCr(3N-2,N) different "middle means". (For large N that is not significantly fewer than all the nCr(3N,N) possible ways to sum N of these numbers.)

Of course that's only the worst case, and the average case is likely much better. And even the worst case over inputs that satisfy some reasonable conditions is likely better. Assuming that we are talking about a practical problem (and not a purely theoretical one), then there are likely certain conditions that the input is guaranteed to satisfy. (Whether they can formulate well and whether they can be worked into making a better algorithm is of course another matter.)

And even a brute-force algorithm can potentially be made more efficient.

  • For starters (and that might already be the core of your basic algorithm), there is no need to handle all possible partitions into three sets. It's sufficient to only check all the possible ways to choose N from the 3N numbers. You can easily decide whether the mean of that set is possible as a "middle mean" or not. (Simply compare its mean to the mean of the N smallest and to the mean of the N largest of the 2N remaining numbers.)
  • There are of course simple lower and upper bounds for the middle mean. For example, the middle mean can't be smaller than the mean of the 2N smalles of the 3N numbers, and it can also not be larger than the mean of the 2N largest of the 3N numbers. That might reduce the number of cases to check.
  • And why stop at those overall bounds? While constructing all the possible middle sets, you could maintain dynamic lower/upper bounds on what numbers are still allowed to be added to that set without making a "middle set" impossible. That can significantly reduce the running time, but only if the numbers in the input have a relatively wide range.
2