# Thread: Sorting integers into 3 equal (almost) groups

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. Originally Posted by 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
What does 3 equal groups mean?

The GCD of each group must be equal?

3. Originally Posted by 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).
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. 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!)

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

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

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. Originally Posted by 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.
What sort of "playing" did you do as I have tried may ways and all seem to get way off.

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

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