I have
(#:i.2^20) +/ .* m
to find all the possible combinations of elements and
(#:i.2^20) (+/"1@[ </. +/ .*) m
to sort them by number of elements.
A more efficient way to find the possible sums is
> (] + -@[ |.!.0 ])&.>/ (<"0 m), <(+/m){.1
Which gives a (+/m)-element array where each element represents the number
of ways to get a sum equal to the number at that index.
This method, taken to four dimensions (one for each bucket) and using sparse
arrays, could be promising.
Marshall
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Skip Cave
Sent: Sunday, April 10, 2011 4:31 PM
To: Programming forum
Subject: [Jprogramming] Weight distribution problem
Last month, in a Chat discussion of GPUs, Devon mentioned a group called the
Thalesians (thalesians.com) who were having a public discussion about the
applicability of GPUs to programming problems, particularly in the area of
economic analysis.
http://jsoftware.com/pipermail/chat/2011-March/004109.html
Devon was planning to attend the discussion. The group describes themselves
as (and I quote) "a think tank of dedicated professionals with an interest
in quantitative finance, economics, mathematics, physics, computer science,
and synergetics, not necessarily in that order."
The group was founded in September, 2008, by Paul Bilokon
<http://www.bilokon.co.uk/> (then a quantitative analyst at Lehman Brothers
specialising in foreign exchange, and a part-time researcher at Imperial
College <http://www.imperial.ac.uk/>), and two of his friends and
colleagues: Matthew Dixon <http://www.cs.ucdavis.edu/%7Emfdixon/>
(then a quantitative analyst at Deutsche Bank) and Saeed Amen
<http://www.saeedamen.com/> (then a quantitative strategist at Lehman
Brothers). They were joined by the first Thalesians: John Aston, Thomas
Barker <http://thomasbarker.com/>, Jeremy Cohen
<http://www.internetcentre.imperial.ac.uk/projects>, Paul Davis, Nikolai
Iordanov, Jayshan Raghunandan, Rene Reinbacher, and Steve Zymler, and
others.
When I looked at their web page, I came across a problem that one of the
Thalesians (Paul) had posted on their site. The problem asked for a general
solution to a problem where there is a number of masses of different values
which are to be distributed among a few buckets. The problem is to
distribute the masses such that the difference in mass between the filled
buckets is minimized. You can see the full problem at the bottom of the
Thalesian site home page. I won't copy the full problem here from their web
page, as it uses embedded GIF images for the equations.
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.
Looking at the problem, if
m =. 23 43 12 54 7 3 5 10 54 55 26 9 9 43 54 1 8 6 38 33
then the masses in each bucket will likely be close to
(+/m) % 4
123.25 NB. the perfect distribution
However, since there are no fractional masses, the solution will likely be
some combination of integer masses around 123. My thought was to explore
what different combinations of masses sum to values around 123.
If we use the combination function "comb" we can generate indicies of all
possible groups of 3, 4, 5, 6, 7, etc.. Then we can generate the actual
combinations and their sums thusly:
cs3 =. +/"1 (3 comb 20) { m
cs4 =. +/"1 (4 comb 20) { m
cs5 =. +/"1 (5 comb 20) { m
cs6 =. +/"1 (6 comb 20) { m
cs7 =. +/"1 (7 comb 20) { m
($cs3), ($cs4), ($cs5), ($cs6), ($cs7)
1140 4845 15504 38760 77520
So nowt t would be useful to find out how many combinations taken 3, 4, 5,
6. and 7 at a time, add up to 121, 122, 123, 124, or 125
+/ cs3 = 121
5
+/ cs3 = 122
0
+/ cs3 = 123
6
.............
this seems like a long way to do this. I'm sure that there is a way to find
all of the sums I want from all of the combinations in a single J statement.
What is it?
Ideally, now would be the time to determine what different combinations of
integers around 123, when taken four at a time, will add up to the sum of m
(+/m) or 493
c =. (4 $ 121), (4 $ 122), (4 $ 123), (4$ 124), (4 $ 125)
$c
20
$ 4 comb 20
4845 4
+/ 493 = +/"1(4 comb 20) { c
672
So there are 672 combinations of the numbers 121 - 126 that sum to 493
Now I just need to match the combinations of 3-7 weights to the 672
combinations of each bucket sum.
Any clues how to do this in J?
Skip
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
