Page 1 of 2 12 LastLast
Results 1 to 10 of 11

Thread: Sorting integers into 3 equal (almost) groups

  1. #1

    Sorting integers into 3 equal (almost) groups

    So I have this problem which I need to solve, I have a group of integers which I want to sort into 3 equal groups. The data which I need to sort is:
    3169, 3063, 3061, 3054, 3018, 3013, 2979, 2943, 2833, 2824, 2794, 2759, 2722, 2701, 2602, 2594, 2577, 2568, 2514, 2466, 2466, 2425, 2364, 2359, 2941, 1910, 1900, 1317, 1115, 2248, 2163, 1969, 2258, 3074, 1241


    I don't mind if the data does not fully match up into equal groups however they must remain in tact (E.G. one number cannot be halved into two groups, they must remain how they are).
    The same number of integers do not need to be in the same group (E.G. one group could contain integers while another could only contain 6, as long as the integers equal the same/similar overall values).


    Does anyone have any ideas how to start this as I am completely clueless, all I can think is trial and error

  2. #2
    Elite Member
    Join Date
    Jun 2007
    Posts
    17,058
    Quote Originally Posted by William444555 View Post
    So I have this problem which I need to solve, I have a group of integers which I want to sort into 3 equal groups. The data which I need to sort is:
    3169, 3063, 3061, 3054, 3018, 3013, 2979, 2943, 2833, 2824, 2794, 2759, 2722, 2701, 2602, 2594, 2577, 2568, 2514, 2466, 2466, 2425, 2364, 2359, 2941, 1910, 1900, 1317, 1115, 2248, 2163, 1969, 2258, 3074, 1241


    I don't mind if the data does not fully match up into equal groups however they must remain in tact (E.G. one number cannot be halved into two groups, they must remain how they are).
    The same number of integers do not need to be in the same group (E.G. one group could contain integers while another could only contain 6, as long as the integers equal the same/similar overall values).


    Does anyone have any ideas how to start this as I am completely clueless, all I can think is trial and error
    What does 3 equal groups mean?

    The GCD of each group must be equal?
    “... mathematics is only the art of saying the same thing in different words” - B. Russell

  3. #3
    Junior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    167
    Quote Originally Posted by William444555 View Post
    So I have this problem which I need to solve, I have a group of integers which I want to sort into 3 equal groups. The data which I need to sort is:
    3169, 3063, 3061, 3054, 3018, 3013, 2979, 2943, 2833, 2824, 2794, 2759, 2722, 2701, 2602, 2594, 2577, 2568, 2514, 2466, 2466, 2425, 2364, 2359, 2941, 1910, 1900, 1317, 1115, 2248, 2163, 1969, 2258, 3074, 1241

    I don't mind if the data does not fully match up into equal groups however they must remain in tact (E.G. one number cannot be halved into two groups, they must remain how they are).
    The same number of integers do not need to be in the same group (E.G. one group could contain integers while another could only contain 6, as long as the integers equal the same/similar overall values).
    You will have to clarify the goal; one way to do so would be to put the question in context. Knowing why you need to do this would help us be sure what you need to do.

    If what you mean is that you want to partition this set of numbers into three subsets, each of which has the same SUM, then I would start by adding them all up and dividing by 3 to find what the sum of each subset would have to be. Then I would use what amounts to intelligent trial and error, forming three subsets that are somewhat close and trying exchanges between them to get closer to equality.

  4. #4
    Elite Member
    Join Date
    Feb 2004
    Location
    Ottawa, Ontario
    Posts
    16,654
    Looks like impossible task; even if total is divisible by 3.
    Take this simple example:
    1,3,4,7,8,13

    Sum is 36, so each group must add to 12: can't be done.

    Btw, the total of the numbers in your list is 88004,
    which is not divisible by 3. (unless I goofed!)
    I'm just an imagination of your figment !

  5. #5
    Junior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    167
    As Denis said, an exact solution is impossible for your list of numbers, so you would have to depend on your word "almost"! How close is "almost"?

    I tried playing with the problem using a spreadsheet to speed up the additions, and found a partition that is reasonably close without wasting too much time on it. The most appropriate way to do it would be a computer program; that would be largely a matter of trying out many possible partitions and trying to minimize the deviations.

    Please reply and let us know more about the problem.

  6. #6
    Junior Member
    Join Date
    Nov 2017
    Location
    Rochester, NY
    Posts
    167
    You haven't responded to confirm my interpretation of the problem, or tell us what constitutes "close enough".

    I did play a little more with the numbers, and was able to get three subsets with sums of 29,334, 29,335, and 29,335, which is the best you could possibly do. But, as I said, I found it by "playing", just trial and error, so apart from little tricks I learned by doing it, there is nothing to tell you about a general method you could use for other numbers.

  7. #7
    Quote Originally Posted by Dr.Peterson View Post
    As Denis said, an exact solution is impossible for your list of numbers, so you would have to depend on your word "almost"! How close is "almost"?

    I tried playing with the problem using a spreadsheet to speed up the additions, and found a partition that is reasonably close without wasting too much time on it. The most appropriate way to do it would be a computer program; that would be largely a matter of trying out many possible partitions and trying to minimize the deviations.

    Please reply and let us know more about the problem.
    This is what I was thinking, but I'm not sure how to get the data into an algorithm of sorts which will put the integers into 3 groups which are the closest to each other.

  8. #8
    Quote Originally Posted by Dr.Peterson View Post
    You haven't responded to confirm my interpretation of the problem, or tell us what constitutes "close enough".

    I did play a little more with the numbers, and was able to get three subsets with sums of 29,334, 29,335, and 29,335, which is the best you could possibly do. But, as I said, I found it by "playing", just trial and error, so apart from little tricks I learned by doing it, there is nothing to tell you about a general method you could use for other numbers.
    What sort of "playing" did you do as I have tried may ways and all seem to get way off.

  9. #9
    Elite Member stapel's Avatar
    Join Date
    Feb 2004
    Posts
    15,521

    Cool

    Quote Originally Posted by William444555 View Post
    What sort of "playing" did you do as I have tried may ways and all seem to get way off.
    Please reply with a clear listing of the "many ways" you "have tried", and your results, so we can see what's going on. When you reply, please include information on the math class that generated this exercise, recent topics of study, what results or rules you think you may be expected to apply, and a definition of "close enough" for this exercise. Also, if you are expected to construct an algorithm, what computer language(s) do you know, etc. Thank you!

  10. #10
    Elite Member
    Join Date
    Feb 2004
    Location
    Ottawa, Ontario
    Posts
    16,654
    Quote Originally Posted by William444555 View Post
    This is what I was thinking, but I'm not sure how to get the data into an algorithm of sorts which will put the integers into 3 groups which are the closest to each other.
    That's a significan't change to your original problem.

    Without thinking much, how about:
    1: arrange the data in ascending order
    2: add and establish 1/3 amount: x = 1/3(SUM)
    3: get group1 starting at high end, then "patching"
    from low end to get as close as possible to x
    4: similarly for group2
    5: group3 would end up being the "leftover"

    Just a thought: still on my 1st coffee...
    I'm just an imagination of your figment !

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •