I have a problem on my hands, and would like help matching it to the existing, studied problems. I explain it like so:

I have a sequence of $n$ equal-sized glasses of water. Each has a different amount of water inside, some are very full, some are near empty, and some completely empty. I can pour water from one glass into another, but have no way of measuring how much water each pour removes/adds from the glasses. I can only perform a pour and then compare the levels of the glasses again. Pours are "atomic", meaning a roughly fixed amount of water is transferred with each one (I cannot make pours of different sizes). What steps do I need to follow to equally distribute all the water among the glasses?

An initial algorithm I have come up with is to sort the glasses in order of fullness. Then I take the most and least full, and do one pour of water. I repeat, again taking the least full glass and the most full glass, and doing one pour. Repeat until all glasses are roughly equal.

Does a general problem exist that is similar to this?

In the interest of avoiding the XY problem, here is the reason I am interested in this: I am writing a routine that iteratively adjusts the probability thresholds for multinomial classification. I can nudge each threshold in either direction, and my aim is to have each class be equally likely. However, I will not know what impact each "nudge" has until I've done it, re-fitted the classifier and gotten predictions. I then use the outputted predictions to calculate the probability of each class. The above explanation is my attempt to describe what I need it to do.

  • 1
    $\begingroup$ (Step zero: Check that the lowest rim is above the highest bottom. Refuse to proceed if not.) $\endgroup$
    – greybeard
    Jul 1, 2021 at 14:21
  • $\begingroup$ @greybeard That is clever, I had not considered edge cases like that! In my case I wouldn't worry about it, I've edited my post accordingly. $\endgroup$ Jul 1, 2021 at 14:42
  • 1
    $\begingroup$ Does a pour from glass A to glass B continue until either glass A is empty or glass B is full (whichever comes first)? Or can we decide we want to pour only a little bit of water? If less, can we specify how much should be poured? I don't understand exactly what operations can be performed and what degrees of freedom are available to the algorithm. $\endgroup$
    – D.W.
    Jul 2, 2021 at 8:16
  • $\begingroup$ @D.W. I have tried to clarify a bit more. Imagine tilting the glass for half a second so a bit of water pours out. You can do this multiple times to transfer a lot of water, or just once to transfer a little bit. I have made this the only possibility. That is in order to match the actual scenario, which I have explained at the bottom of the post. $\endgroup$ Jul 2, 2021 at 9:47
  • $\begingroup$ This is the problem of computing the earth mover's distance between your original distribution and the uniform distribution, but under some constraints that prefer you from knowing the original distribution. $\endgroup$
    – D.W.
    Jul 2, 2021 at 16:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.