# 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 Commented Dec 29, 2014 at 18:33
• @belisarius, That is by design. If possible, I would like to randomly get n solutions to this problem. Commented Dec 29, 2014 at 18:34
• But ...how many clusters? How many elements per cluster? Commented Dec 29, 2014 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) Commented Dec 29, 2014 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. Commented Dec 29, 2014 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? Commented Dec 29, 2014 at 18:49
• They aren't the same size ... Commented Dec 29, 2014 at 18:50
• Oh, my bad. Looks good then, I'll try on larger data sets and see how performance is. Thank you. Commented Dec 29, 2014 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. Commented Dec 29, 2014 at 19:18
• @soandos Thread[]` doesn't work that way ... Commented Dec 29, 2014 at 19:20