Results 1 to 14 of 14

Math Help - Creating equal sets from random numbers

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by redkins View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2009
    Posts
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by redkins View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by redkins View Post
    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.


    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by aidan View Post
    "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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2009
    Posts
    4
    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.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by redkins View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by redkins View Post
    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 S_1, S_2, S_3 with element sums t_1, t_2, t_3 respectively, in such a way that

    |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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by alunw View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by awkward View Post
    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 S and there are to be N groups of M we want to minimise:

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

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

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

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

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

    Also huristic algorithms do fall within the purvue of mathematics.

    CB
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    Quote Originally Posted by CaptainBlack View Post
    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 S and there are to be N groups of M we want to minimise:

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

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

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

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

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

    Also huristic algorithms do fall within the purvue of mathematics.

    CB
    Suppose you had a quantum computer. Which of  O_1 ,  O_2 or  O_3 be the most tractable? Grover's search algorithm would probably be best right?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Jul 2009
    Posts
    4
    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.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equal power sets -> Equal sets?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 5th 2012, 10:23 AM
  2. Creating open sets from closed ones
    Posted in the Differential Geometry Forum
    Replies: 7
    Last Post: September 21st 2011, 11:28 AM
  3. Replies: 1
    Last Post: August 29th 2011, 03:18 AM
  4. Replies: 3
    Last Post: October 9th 2010, 03:39 AM
  5. Replies: 3
    Last Post: October 16th 2008, 12:21 AM

Search Tags


/mathhelpforum @mathhelpforum