2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ "I only want each cluster to have a sum of 15 or fewer" is very lax. You still have way too many possible combinations $\endgroup$ – Dr. belisarius Dec 29 '14 at 18:33
  • $\begingroup$ @belisarius, That is by design. If possible, I would like to randomly get n solutions to this problem. $\endgroup$ – soandos Dec 29 '14 at 18:34
  • $\begingroup$ But ...how many clusters? How many elements per cluster? $\endgroup$ – Dr. belisarius Dec 29 '14 at 18:36
  • $\begingroup$ 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) $\endgroup$ – soandos Dec 29 '14 at 18:38
  • 2
    $\begingroup$ 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. $\endgroup$ – David G. Stork Dec 29 '14 at 18:38
2
$\begingroup$ 
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}} *)
Improve this answer
$\endgroup$
13
  • $\begingroup$ Is there a way to do this without holding all sets to be the same size? $\endgroup$ – soandos Dec 29 '14 at 18:49
  • $\begingroup$ They aren't the same size ... $\endgroup$ – Dr. belisarius Dec 29 '14 at 18:50
  • $\begingroup$ Oh, my bad. Looks good then, I'll try on larger data sets and see how performance is. Thank you. $\endgroup$ – soandos Dec 29 '14 at 18:51
  • $\begingroup$ 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. $\endgroup$ – soandos Dec 29 '14 at 19:18
  • $\begingroup$ @soandos Thread[] doesn't work that way ... $\endgroup$ – Dr. belisarius Dec 29 '14 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.