# Partitioning a list in n sublists with constrains in their sums

Is there a way to put cluster level limits on clusters? For example, if I run:

FindClusters[{1, 2, 3, 4, 4, 6, 7, 10}]


I get back two lists, {{1, 2, 3, 4, 4}, {6, 7, 10}}. But lets say I only want each cluster to have a sum of 15 or fewer and potentially get {{2, 3, 10}, {6, 3, 1}, {7, 4, 4}}

As far as I can tell, this is not possible to express with a distance function, so maybe clustering is the wrong tool for the job?

Is there a way to do that?

• "I only want each cluster to have a sum of 15 or fewer" is very lax. You still have way too many possible combinations Dec 29 '14 at 18:33
• @belisarius, That is by design. If possible, I would like to randomly get n solutions to this problem. Dec 29 '14 at 18:34
• But ...how many clusters? How many elements per cluster? Dec 29 '14 at 18:36
• Ideally, I'd like to be able to just give a number of clusters (in the case, 3). Max elements per cluster should not matter unless they meet that limiting condition (also, the inversion of the limiting condition could exist, so that would mean 3 clusters of fewer) Dec 29 '14 at 18:38
• Clustering is based on similarity of elements, but your condition is not explicitly based on similarity. For you, the clusters {4, 5, 6} and {1, 14} each sum to 15, but differ drastically as far as clustering algorithms. It seems you want to use Tuples with constraints, not FindClusters. Dec 29 '14 at 18:38

Quiet[<< Combinatorica;]
l = {1, 2, 3, 4, 4, 6, 7, 10};
f[l_, n_, min_, max_] := Module[{part, s},
While[(s = (Tr /@ (part = RandomKSetPartition[l, n]));
Not[And @@ Thread[min < s < max]])];
part]
f[l, 3, 5, 15]
(* {{1, 10}, {2, 4, 7}, {3, 4, 6}} *)

• Is there a way to do this without holding all sets to be the same size? Dec 29 '14 at 18:49
• They aren't the same size ... Dec 29 '14 at 18:50
• Oh, my bad. Looks good then, I'll try on larger data sets and see how performance is. Thank you. Dec 29 '14 at 18:51
• This is silly, but I can't seem to bound it both ways (between min and max). Replacing the inside with Module[{part, s}, While[Or @@ Thread[s = (Tr /@ (part = RandomKSetPartition[l, n])) < max && s > min] gives nonsensical answers. Dec 29 '14 at 19:18
• @soandos Thread[]` doesn't work that way ... Dec 29 '14 at 19:20