I need to find a way or an algorithm that groups members of a given data set (of positive integers) so that the difference between group means is minimized (not maximized, as usual).
There are two constraints:
- The number of groups should not exceed log(N) base 2. N is the input array size. Let us assume that N = 16, always.
- The size of the group should be at least log(N) base 2. In the below example, the size of the group should be at least 4.
By searching on the WEB, I have found the following greedy algorithm. Please also see below example.
- sort the numbers in the descending order
- take the first K elements and put them into different groups. Here, K is the number of groups.
- for the next (N - K) elements, put them in the group with the lowest sum. repeat this until completion of all the numbers.
Can we get a better algorithm in terms of time complexity? Guidance toward a better solution to this problem is appreciated.
Example:
for input array = (11, 11, 14, 16, 17, 18, 18, 19, 20, 21, 22, 25, 25, 26, 28, 31)
The solution: (where sd: standard deviation, cv: coefficient of variation)
group mean sd cv
(31, 20, 17, 11) 19.8 8.4 0.4
(28, 21, 18, 11) 19.5 7.1 0.4
(26, 21, 19, 14) 20.0 5.0 0.3
(25, 22, 18, 16) 20.3 4.0 0.2