Simple question: find all middle means
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
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.