Is there an algorithm for finding the 10 best combinations from a list of 50 parts? I've been thinking about a problem that seems pretty generic but I can't seem to find a solution for..
I have a list of 50 values. I need to make 10 groups which are as uniform as possible with regard to the mean per group and as uniform as possible within the group. 
I realize this is a problem with two criteria and that doesn't make it easier. The most important task is that all groups have a very similar mean value. The deviations within the group should be smaller than a certain value.
I try to find a solution with a python script just rolling over all combinations Of course this would result is a huge amount of combinations. Therefore I try to limit this number by setting a tight criterium for the deviations within the group and limiting the means of the groups to a small range.
Still this runs very long and up to now no solution has been found.
What are your ideas for finding a solution?
 A: My answer does not give you the best solution (probably) but a reasonably good one.
First of all you should define a performance measure that you want to optimize. 
Let $C_1, ..., C_5$ be the 5 partitions, you could e.g. use 
$\sum_{i=1}^5\sum_{x\in C_i}(\overline{x}_i-x)^2+ C\sum_{i=1}^n(\overline{x}_i-\overline{x})^2$ as a loss function, where $\overline{x}_i$ is the mean in group $i$ and $\overline{x}$ is the overall mean. $C$ is a parameter that controls the trade off between your two goals. 
You could then utilize a greedy search algorithm with the following pseudocode:


*

*initialize a starting partition $C_1^{[0]}, ..., C_5^{[5]}$

*calculate the performance measure for each change of values $x_i, x_j (i \neq j)$ and exchange those values that minimize the performance measure, resulting in partition $C_1^{[m]}, ..., C_5^{[m]}$

*repeat step 2 until there is no change in performance measure

*repeat step 1. -3. with different initial configurations 

*Output the best solution 

A: Sounds roughly equivalent to the Knapsack problem. The optimal solution for this problem is NP complete.  In non CS terms, you aren't going to find an "efficient" optimal algorithm, and the run-time of any algorithm that finds an optimal solution will increase exponentially (or worse) as N increases. 
As such your options are approximations if you don't want this to take 100 years for it to compute a solution for 100 elements. K means is one such method commonly used to perform clustering on N dimensional vectors with minimum variance.
Your issue is that you'll need to perform initialization, and the simplest most common way to do that is by selecting N (in your case, 10) random values. This is not guaranteed to give good solutions, so you may have better heuristics to select these "seed" points.
Once you have initilization down, the algorithm is pretty straight forward:
#(L2 norm is pretty common, AKA euclidean distance, this works for any dimension, so will work for scalars)
choose a distance metric 
initialize N centroids
#will need to initialize centroids e.g the random point method
create array of N clusters, each cluster containing an array of points and a centroid
While true:
    For each element in elements:
        find closest value to cluster with distance metric.
        add element to closest cluster
        update closest cluster centroid according to mean of current elements in cluster
    if means of all cluster centroids haven't changed much since last iteration:
        exit, we have reached convergence
    else:
        empty each cluster, but keep the centroids

Over time kmeans will adjust centroids to the surrounding values, until convergence is met (or you decide enough iterations have taken place) and you'll get your 10 clusters as a result.  There are other methods that work similarly listed as well on the Wikipedia page, like k medioids and k medians, which may or may not be better for your problem.  
