Sorting integers into 3 equal (almost) groups

[William444555]

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

 

[Deleted member 4993]

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?

 

[Dr.Peterson]

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.

 

[Dr.Peterson]

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.

 

[Dr.Peterson]

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.

 

[William444555]

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.

 

[William444555]

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.

 

[stapel]

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!

 

[Dr.Peterson]

What sort of "playing" did you do as I have tried may ways and all seem to get way off.

As others have said, we REALLY need to know the context of the question. You originally gave the impression that you just need to work it out for this one set of numbers, but now you say you want a general algorithm. Do you mean you want to program it, or something else? In any case, what are the details of the more general question, and why do you need to do it? If it is for an assignment, quote exactly what you are to do. If it is just for you, tell us why.

As to what I did, I made a spreadsheet in which I first sorted the numbers, then could enter 1, 2, or 3 next to each of them, which would put it into a column that would be added up and compared to the goal. I initially assigned the numbers 1, 2, 3, 1, 2, 3, ..., and then looked for pairs I could interchange to get closer to the goal. Eventually I couldn't directly improve it, so I would just change some pair to "shake up" the problem and hopefully get on a path to a better solution. This is just a heuristic, not an algorithm; but it might be necessary to take such an approach, since there are otherwise quadrillions of possible partitions to try. (But only a complete search could prove that you have the best possible answer, if you can't find one that is as close as possible like mine.)

My starting with alternating columns was important, as it ensured that there would be numbers close to one another in all three columns, so that I could interchange pairs to make small adjustments.