ELISHEVA,
I have provided an example in another post that demonstrates that the algorithm does not always produce optimal results. You asked about how I was going to unrestricted integer partitions and combinatorials to find such an example. In a nutshell, it would be a brute force solution for a given data set to find the optimal solution for all possible groupings.

Let's say for my data set, I generate 12 random values ranging between 15 and 30. First, I need to know every single possible grouping. This can be accomplished using unrestricted integer partitioning (see RFC: Integer::Partition::Unrestricted and Re: Generator of integer partitionts of n for more details). Knowing that 1 possible way of breaking 12 into groups is 6/6 does me no good by itself.

At this point, there are two options. You could generate all possible permutations of the list and then gather them using your integer partition. For instance, if the current iteration of your integer partition were (2, 3, 3, 4) then you would take the first 2, next 3, etc. Determine the averages, get the next permutation, wash rinse repeat. You would use a watermark algorithm to keep track of "best" and you could stop the second you find one that the heuristic solution fails to produce.

Alternatively, you could create an arbitrarily nested loops solution using combinations. You could take each bucket in the unrestricted integer partition iteration and generate all possible combinations - perhaps using Re: Iterating over combinations. You then need to remove those used items from the list to generate the next bucket. This is a wash-rinse-repeat algorithm outlined in Arbitrarily Nested Loops.

Most of this work I had already done in the permutations of groups link I originally pointed to. I hope that explains.