25 Jan, 2010, shasarak wrote in the 1st comment:
Votes: 0
Okay, algorithm question.

Imagine you have a pile of a couple of dozen rocks, all with different weights. You need to divide them into three piles in such a way that all three piles end up as closely as possible the same total weight as each other; in other words, there mustn't be another combination which would result in the three pile-weights being more similar to one another. What's the optimum way to do this?

I'm currently thinking that if you begin by sorting the rocks into descending order of weight, then add each one in turn to whatever the lightest pile is at that point, that should get you somewhere close; but is there a better way?
25 Jan, 2010, Scandum wrote in the 2nd comment:
Votes: 0
Don't know of an optimum way, but a generic way is to put the heaviest and lightest stone in pile A, 2nd heaviest and 2nd lightest stone in pile B, and continue in that fashion till all stones are used. If you have a very large amount of rocks that will work very well, but with fewer rocks it'll be less precise.
25 Jan, 2010, David Haley wrote in the 3rd comment:
Votes: 0
Scandum's algorithm assumes that the stone weights have some kind of uniform/normal weight distribution. You can see that it fails considerably when you have a very small number, not a multiple of 3, of very large stones and a very large number of much smaller stones. You can't just distribute things into the piles in order. Your approach (Shasarak's) is basically a greedy algorithm and will work better than Scandum's. I'd have to think longer to see if it's the best that can be done.

This reminds me of a somewhat well-known algorithm problem. I'll kick this around in my head for a while and get back to you…
25 Jan, 2010, Chris Bailey wrote in the 4th comment:
Votes: 0
Ruby Quiz has an article discussing this particular problem, and several user submitted solutions. In their example the idea is to evenly split loot amongst several adventurers, based on the value of each bit of loot.

Rubyquiz - Splitting The Loot


Might be an interesting read, I had another solution ( I went through trying to solve all of the ruby quizzes awhile back), but I seem to have misplaced it. Good luck! =)
25 Jan, 2010, David Haley wrote in the 5th comment:
Votes: 0
Glancing over that page, it looks like it only tells you if it's possible to divide things fairly, which is a different problem than finding the "least unfair" solution if there is no fair solution.

You can think of Shasarak's problem as minimizing the distance between groups; really there's any number of way of thinking about it, and once a good one is hammered out the solution should follow rather clearly.
25 Jan, 2010, Chris Bailey wrote in the 6th comment:
Votes: 0
DH - Looking a bit closer, you are correct! It had been awhile since I messed with it, so I had forgotten. I can't work on it at the moment as I don't have a programming environment set up on this PC. I will work on something this evening though. =)
25 Jan, 2010, David Haley wrote in the 7th comment:
Votes: 0
A brute force approach is to compute all possible divisions into three sets, and then rank the divisions by the sum of differences of the three piles' weights, or something like that. The strictly fair solution will have a rank of zero; the "most fair" solution will be the one with the lowest rank.

Off the top of my head, the number of possible divisions into three sets is 3^n, where n is the number of elements you have. (Reasoning: for each of the n elements, you must choose which of the three piles to put it into. Therefore you are making n choices with three options each time.)

For 12 elements, you have half a million divisions to check. At 18, you have 387,420,489 divisions to check. It gets pretty ridiculous after that. Obviously a better solution is needed for interesting values of 'n'. However, this is a good way of checking that whatever algorithm you have is behaving correctly at least for small numbers of n. (It still might not be fully correct, but if it fails on n < 12 you know that it's wrong.)
25 Jan, 2010, Tyche wrote in the 8th comment:
Votes: 0
What if you have one rock?
25 Jan, 2010, elanthis wrote in the 9th comment:
Votes: 0
Shasarak, I think your method is the best you're going to get without going into a land of nightmare and dead kittens. Your algorithm is exactly what I would go with in your situation.
26 Jan, 2010, David Haley wrote in the 10th comment:
Votes: 0
Tyche said:
What if you have one rock?

Then the problem is solved trivially, because no matter where you put the rock, you have reached the most fair way of distributing that rock. (By definition, it's the most fair, because it's the only way. It's also the least fair…)

elanthis said:
Shasarak, I think your method is the best you're going to get without going into a land of nightmare and dead kittens. Your algorithm is exactly what I would go with in your situation.

Greedy algorithms are not always as bad as people think. In fact, they are sometimes optimal! So it's possible that this is already an optimal algorithm.

The problem here for me is that it's not clear what exactly we're trying to optimize. Are we trying to minimize the standard deviation of the sums of weights in each pile? Or something else? What exactly is meant by "similarity"?
26 Jan, 2010, Lyanic wrote in the 11th comment:
Votes: 0
I was somewhat unsure if "optimum way to do this" meant "find the best solution" or "find the best solution as computationally efficiently as possible".

As far as just finding the best solution, I vaguely recall a dynamic programming approach to solving this/a similar problem. I don't have time to search for it right now, though. Maybe if this discussion is still ongoing later in the week, I will try to track it down and post it.
26 Jan, 2010, Tyche wrote in the 12th comment:
Votes: 0
David Haley said:
Tyche said:
What if you have one rock?

Then the problem is solved trivially, because no matter where you put the rock, you have reached the most fair way of distributing that rock. (By definition, it's the most fair, because it's the only way. It's also the least fair…)


That's for Shasarak to answer as he posed the problem.

Second question to Shasarak is
Can I use a sledgehammer to break up rocks?

Third question to all. This is optional.
Of those who have posted up to this point, which of you is primarily left-handed?
26 Jan, 2010, Chris Bailey wrote in the 13th comment:
Votes: 0
I am primarily left-handed.
26 Jan, 2010, Scandum wrote in the 14th comment:
Votes: 0
My mother is primarily left-handed.

What might work better than adding to the lowest pile is calculating the optimal distribution (total weight / 3) - then fill up the first pile as good as possible, then do the second and third one. This however has the downside that the first pile typically contains the large rocks, and the third pile the small rocks. You'd have to run a simulation to see which gives the best result, but probability should favor this approach.
26 Jan, 2010, David Haley wrote in the 15th comment:
Votes: 0
Scandum said:
What might work better than adding to the lowest pile is calculating the optimal distribution (total weight / 3) - then fill up the first pile as good as possible, then do the second and third one. This however has the downside that the first pile typically contains the large rocks, and the third pile the small rocks. You'd have to run a simulation to see which gives the best result, but probability should favor this approach.

Why, exactly, do you say that "probability should favor this approach"? Well, anyhow, it fails on fairly simple cases. I suspect that it fails in general because it completely ignores trying to evenly distribute, it just stuffs things in thoughtlessly.

Anyhow, consider this case:
20,10,5,4,3,2,1
Total: 45
45/3 = 15
So your algorithm will do:
Pile 1: 10, 5
Pile 2: 4,3,2,1
Pile 3: 20
(note that it could have chosen 20 for 2 and 4,3,2,1 for 3 – it makes no difference)

thus making for totals of 15, 10 and 20.
Shasarak's greedy algorithm will do:

Pile 1: 20
Pile 2: 10,2
Pile 3: 5,4,3,1

Note that it could have put the "1" in either 2 or 3, because both were 12 as we were going to put things in.

This gives us totals of 20, 12 and 13. Clearly, the std dev of 12,13,20 is less than the std dev of 10, 15, 20.

Anyhow, this illustrates its failure, and hopefully why it failed should be clear as well (as mentioned above it's because it doesn't even try to distribute evenly). Perhaps you can give an example where your approach produces a better result than the greedy algorithm. If indeed "probability favors" your approach, you should be able to generate a number of random stone sets, and yours should on average beat Shasarak's…
26 Jan, 2010, elanthis wrote in the 16th comment:
Votes: 0
shasarak said he wanted a solution that resulted in there being no other distribution that had the three piles being closer together; in other words, the least deviation.
26 Jan, 2010, David Haley wrote in the 17th comment:
Votes: 0
That's what I thought too. But it might also be the case where you might prefer to get two perfectly aligned and one off, rather than all three more evenly spaced out. (I went with std dev because it's the easiest to express and grok.)
26 Jan, 2010, Scandum wrote in the 18th comment:
Votes: 0
First set of numbers I tried:

10, 9, 8, 7, 6, 5, 4

49 / 3 = 16

My method:

10, 6 = 16
9, 7 = 16
8, 5, 4 = 17

Shasarak's method

10, 5, 4 = 19
9, 6 = 15
8, 7 = 15
26 Jan, 2010, David Haley wrote in the 19th comment:
Votes: 0
Fair enough. I still am not convinced that "probability favors" the approach. I suspect that your approach will work when the numbers have certain properties, namely a fairly even distribution. When you start messing up the distribution, your algorithm doesn't do as well.
I guess one way to put it is that your algorithm is locally greedy whereas Shasarak's is globally greedy.

Clearly, though, we've shown at this point that neither one is optimal! :wink:
26 Jan, 2010, shasarak wrote in the 20th comment:
Votes: 0
elanthis said:
shasarak said he wanted a solution that resulted in there being no other distribution that had the three piles being closer together; in other words, the least deviation.

Yes. :smile:

If you want it expressed formally, then I want to minimise the weight difference between the heaviest pile and the lightest one.
0.0/32