# Creating equal sets from random numbers

• Jul 7th 2009, 04:31 AM
redkins
Creating equal sets from random numbers
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.
• Jul 7th 2009, 05:09 AM
malaygoel
Quote:

Originally Posted by redkins
I need a function to group them into three sets with as close to the same value as possible. I hope that's clear.

What is meant by "sets with as close to the same value as possible"?

Give example what you want.
• Jul 7th 2009, 07:57 AM
redkins
Thanks for getting back Malay.

So what I mean is this; given a set of 9 numbers like

200, 210, 199, 300, 345, 298, 189, 345, 456,

I would like to group them like

200, 345, 298 (843)
210, 456, 189 (855)
300, 345, 199 (844)

Hope that makes more sense.
• Jul 7th 2009, 08:04 AM
malaygoel
Quote:

Originally Posted by redkins
Thanks for getting back Malay.

So what I mean is this; given a set of 9 numbers like

200, 210, 199, 300, 345, 298, 189, 345, 456,

I would like to group them like

200, 345, 298 (843)
210, 456, 189 (855)
300, 345, 199 (844)

Hope that makes more sense.

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.
• Jul 7th 2009, 01:02 PM
aidan
Quote:

Originally Posted by redkins
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.

"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.

• Jul 8th 2009, 12:16 AM
Swlabr
Quote:

Originally Posted by aidan
"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...

The "twist", so to speak, is that the numbers in the set must sum to very close values. See redkins' second post.

redkins - does it matter if the solution is the best possible or not?
• Jul 8th 2009, 01:22 PM
redkins
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.
• Jul 8th 2009, 01:43 PM
CaptainBlack
Quote:

Originally Posted by redkins
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.

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
• Jul 8th 2009, 02:08 PM
awkward
Quote:

Originally Posted by redkins
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.

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 $\displaystyle S_1, S_2, S_3$ with element sums $\displaystyle t_1, t_2, t_3$ respectively, in such a way that

$\displaystyle |t_1 - t_2| + |t_2 - t_3| + |t_1 - t_3|$

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.
• Jul 8th 2009, 04:13 PM
alunw
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.
• Jul 8th 2009, 05:21 PM
awkward
Quote:

Originally Posted by alunw
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.
• Jul 8th 2009, 10:42 PM
CaptainBlack
Quote:

Originally Posted by awkward
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 $\displaystyle S$ and there are to be $\displaystyle N$ groups of $\displaystyle M$ we want to minimise:

$\displaystyle O_1=\sum_i (s_i-S/N)^2$

or if you don't want to use the mean you can minimise something like:

$\displaystyle O_2=\sum_{i \ne j} |s_i-s_j|$

$\displaystyle O_3=\sum_{i \ne j} (s_i-s_j)^2$

where $\displaystyle s_i$ is the sum of the $\displaystyle i$ 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 $\displaystyle O_1$).

Also huristic algorithms do fall within the purvue of mathematics.

CB
• Jul 8th 2009, 10:51 PM
Sampras
Quote:

Originally Posted by CaptainBlack
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 $\displaystyle S$ and there are to be $\displaystyle N$ groups of $\displaystyle M$ we want to minimise:

$\displaystyle O_1=\sum_i (s_i-S/N)^2$

or if you don't want to use the mean you can minimise something like:

$\displaystyle O_2=\sum_{i \ne j} |s_i-s_j|$

$\displaystyle O_3=\sum_{i \ne j} (s_i-s_j)^2$

where $\displaystyle s_i$ is the sum of the $\displaystyle i$ 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 $\displaystyle O_1$).

Also huristic algorithms do fall within the purvue of mathematics.

CB

Suppose you had a quantum computer. Which of$\displaystyle O_1$, $\displaystyle O_2$ or $\displaystyle O_3$ be the most tractable? Grover's search algorithm would probably be best right?
• Jul 9th 2009, 12:06 AM
redkins
Wow...I'm glad I managed to pose such a brain teaser! So I reworked the Javascript based on CaptainBlack's suggestion and it seems to work better. I've attached the JavaScript to this post.

Thanks to everyone for your help with this.

Russ.