Hi all,
Let me start by saying I know next to nothing about maths so this may be a high school question and I apologies if it is. It also may not be anything to do with sets but it feels like it might be.
So I have a set of 9 random numbers (in reality they will most likely be between about 150 and 500), and I need a function to group them into three sets with as close to the same value as possible. I hope that's clear.
I need to code this in Javascript or .NET - it's actually for arranging 3 columns of 3 images, so I'd really appreciate it if someone here could point in the direction of how I could do this.
Many thanks,
Russ.
I think that you could find the average of the nine values..then randomly pick two of the values. Next, finish the first set the value such that their sum is closest to the average.
Apply the same for rest six values.
Sorting in the beginning would prove to be very helpful. After you have sorted, for the first set, pick the lowest and the biggest value.
"a set of ... random numbers"
If the numbers are random then you should be able to divide them into the 3 sets with no adjustment required.
for 1 to n
RandomNumber(1) to set A
RandomNumber(2) to set B
RandomNumber(3) to set C
RandomNumber(4) to set A
RandomNumber(5) to set B
RandomNumber(6) to set C
RandomNumber(7) to set A
RandomNumber(8) to set B
RandomNumber(9) to set C
...
RandomNumber(n-2) to set A
RandomNumber(n-1) to set B
RandomNumber(n) to set C
If you require the difference to be at minimum, then you could selectively swap values from the various sets.
Well, I'd like it to be the best solution, but if it's quick and dirty, I could live with that :^)
I've attached an HTML document with the Javascript I came up with based on Malay's suggestion, which you can run in a browser. It kind of works but I'm wondering if it could be improved somehow.
Thanks for your help,
Russ.
You could try this:
Find the average of the nine, then for the first set take the largest the smallest and the one of the seven remaining that makes the total closest to the average (use some form of tie breaking rule if two qualify).
Now repeat with the six remaining numbers.
CB
Despite the discussion thus far, I don't think "as close to the same value as possible" has been defined unambiguously.
Here is one possible definition (not the only one possible):
"Partition the set of 9 numbers into three sets with element sums respectively, in such a way that
is minimized."
I don't know if there is an easy algorithm to solve this problem in this form.
As I said, this is not the only definition possible, and you are free to come up with another one. But I suggest that you need a precise definition of the problem before you can tell whether you have solved it.
You should feel pleased with yourself for having posed a problem that has drawn so many responses.
Although I couldn't swear to it, I think your problem almost certainly belongs in the same class as the "travelling salesman" problem: that means that there is no known algorithm for getting the best solution and that if you wanted to arrange 900 rather than 9 images it would be a highly intractable problem. On the other hand, it is probably the case that a fairly simple algorithm will come within some acceptable margin - say 10 or 15% of the best possible solution, and I'd guess that would be good enough for your purposes.
I'd suggest that sorting the images by size and then picking largest smallest and the one that makes the total closest to the average will be very good, and that with less than about 20 or 30 images will run very quickly.
It's probably far more to the point to make sure your web site is responsive and easy to maintain than to worry about every last pixel in a gallery of images. Although this is completely off-topic and may be irrelevant to what you need to do, have you thought about not using columns at all, and simply using floating objects to display the images.
That would be my choice - that way it is up to the web browser to make the best use of the available screen space.
Hi alunw,
You have a good point, I may have contrived a problem too difficult for the OP's purpose (although, as I said, anyone is free to propose a different definition).
But lacking a definition of "as close to the same value as possible", it seems to me the problem moves out of the realm of mathematics and into the vague territory of heuristic algorithms, where the algorithm simply does what it does and there is no precise criterion for judging success or failure-- just "it's good enough" or "it's not good enough" based on subjective satisfaction or the lack thereof.
There are perfectly good metrics that can be assumed to quantify "as close to the same value as possible. If the sum of all values is and there are to be groups of we want to minimise:
or if you don't want to use the mean you can minimise something like:
where is the sum of the th group.
You just have to go back to the client and determine what is a suitable objective. Without a clear prefernce form the client choose the objective that is most tractable (which in this case I would say is ).
Also huristic algorithms do fall within the purvue of mathematics.
CB