I'm guessing that you could have a few hundred masses distributed across a few dozen buckets, say 500 masses across 30 buckets at an extreme. Even a slightly larger case than the one given, of, say, 40 masses across 8 buckets might cause problems with this sort of approach.
On Mon, Apr 11, 2011 at 7:08 AM, Viktor Cerovski <[email protected]>wrote: > > > Devon McCormick wrote: > > > > These brute force methods may give an answer for very small problems like > > this example but they generally scale very poorly. > > > > On Sun, Apr 10, 2011 at 7:41 PM, Marshall Lochbaum < > > [email protected]> wrote: > > > >> The following verb handily produces the possible distributions given a > >> set > >> of weights. Good luck finding which combinations gave you those sums! > >> > >> NB. x is (#boxes),(upper bound), y is weights to use > >> NB. finds the unique (sorted) sums of groupings of y so that no sum > >> exceeds > >> the upper bound. > >> sums=.4 :0 > >> 'nbox bound'=.x > >> y=.\:~ y > >> s=.,: nbox$0 > >> for_e. y do. > >> s=.(#~ bound >: {."1) ~. \:~"1 ,/ s+"1/ e* =i.nbox > >> end. > >> s > >> ) > >> > >> 4 124 sums m > >> 124 124 124 121 > >> 124 124 123 122 > >> 124 123 123 123 > >> > >> Marshall > >> > >> -----Original Message----- > >> From: [email protected] [mailto: > >> [email protected]] On Behalf Of Viktor Cerovski > >> Sent: Sunday, April 10, 2011 6:45 PM > >> To: [email protected] > >> Subject: Re: [Jprogramming] Weight distribution problem > >> > >> > >> > >> Skip Cave-3 wrote: > >> > > >> > [...] > >> > To make the problem more concrete, Paul gives a specific example of > >> > the problem. There are four buckets, and 20 masses. The masses are 23, > >> > 43, 12, 54, 7, 3, 5, 10, 54, 55, 26, 9, 9, 43, 54, 1, 8, 6, 38, 33 > >> > respectively. What distribution of the 20 masses gives the smallest > >> > mass difference between the four buckets? > >> > > >> > Paul gives a link to his proposed solution, which I have not examined > >> > as yet, since I want to see how far I can get with a J solution. > >> > [...] > >> > > >> After some quick tries with J, I got a bunch of 123 123 123 124 > >> distributions, and they are all mutually different. > >> Here is one of them: > >> > >> conf > >> 0 0 2 3 1 0 3 3 0 2 1 1 2 1 3 1 2 2 1 2 > >> 23 43 12 54 7 3 5 10 54 55 26 9 9 43 54 1 8 6 38 33 > >> > >> +//./conf > >> 123 123 123 124 > >> > >> </./conf > >> ┌──────────┬──────────────┬──────────┬──────────────┐ > >> │23 43 3 54│12 55 9 8 6 33│54 5 10 54│7 26 9 43 1 38│ > >> └──────────┴──────────────┴──────────┴──────────────┘ > >> > > > > I haven't given any method. Which size of the problem > would you consider nontrivial? > > > > > -- > > View this message in context: > > > http://old.nabble.com/Weight-distribution-problem-tp31365679s24193p31366193.html > > Sent from the J Programming mailing list archive at Nabble.com. > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > ---------------------------------------------------------------------- > > For information about J forums see http://www.jsoftware.com/forums.htm > > > > > > -- > Devon McCormick, CFA > ^me^ at acm. > org is my > preferred e-mail > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > > > -- > View this message in context: > http://old.nabble.com/Weight-distribution-problem-tp31365679s24193p31369301.html > Sent from the J Programming mailing list archive at Nabble.com. > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA ^me^ at acm. org is my preferred e-mail ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
