Esme Povirk @madewokherd@computerfairi.es

The naive algorithm is not as slow as I expected, in this case. I suspect that in other cases we'll have a problem.

So, I still have no good solution. I guess we go naive for now.

Turns out I do not understand this as well as I thought. PlaceOrbsInLands in this example (even though that's not quite how I actually wrote it) has a probability of failure that's proportional to the ideal failure probability, for one step, but it's lower than that ideal. For it to be the same, we'd have to stop everything immediately after encountering any failure. But, if it is the same, we end up with an equivalent of trying every permutation.

And now I have to rewrite my placement algorithm because I realized while writing this that I took some shortcuts that may not be valid.

This is actually easy. The probability of stopping based on this specific orb that we placed should be 1/N * (probability of a valid combination based on having placed that orb). Well, the probability of PlaceOrbsInLands failing is equal to the second term in that multiplication, so we can treat this the same as an invalid pairing. It doesn't really matter that there might be some valid ones.

OK, so what if an orb placement succeeds? We still have to place the rest of them. For that, we call PlaceOrbsInLands for our remaining set of lands and orbs. If it succeeds, great. We add the one pair placed in this step, and return the list.

If it fails, we need to decide whether to stop at this step. We want to do that in such a way that the overall probability of returning failure is proportional to the number of valid permutations given our input state.

If we move on to trying a second orb after a failure, and that one also fails, we should return failure a total of 2/N of the time. But we already did the 1/N check, so at this stage we should return failure 1/(N-1) of the time, to increase the total probability to where we need it.

So, for the induction step, we try to place 1 orb.

We have to first account for permutations that fail at that step: we should have an M/N probability of failing outright, where M is the number of invalid orbs for the first land, and N is the total remaining.

So, we can try the orbs in a random order. If the first one fails, we know M is at least one, and so we should randomly return failure 1/N of the time.

The base case (N=1) is simple. If that 1 orb is valid for that 1 land, return a single pair of that land and that orb. If not, return failure.

What I'm trying to do is build this by induction. If I solve the problem for N, I can solve it for N+1. I need a problem statement where that works and is somewhat efficient.

So here it is:
PlaceOrbsInLands(list of lands remaining, list of orbs remaining)

This either returns a list of pairs of lands and orbs, or "failure". Each valid permutation has equal probability, and probability of failure is proportional to the number of invalid permutations.

There's one critical difference though: this allows me to interrupt the process early. If I find an invalid orb placement, I can stop right there and start over. I don't have to calculate the rest of the permutation.

That helps, slightly, but I still expect a lot of retries.

Let's say N is sufficiently small that that algorithm works. Can I make it work for N+1? Yes, here's how:

I need to decide what orb to place in my first land. In order to eliminate bias, I must weigh the probability of each orb by the number of valid permutations with that orb in the given land. I can't calculate that value, but I can just try a random permutation. If it doesn't work, I reroll the first orb. Easy.

Except that's equivalent to the bad naive algorithm.

Except, if I check the permutations in a random order, I don't have to test all of them. I can just choose permutations until I find one that works. That's my naive algorithm from earlier that rerolls way too often and takes too long. But we can build off of that.

The algorithm I settled on is.. maybe more understandable if you start from the end.

Let's say I have N orbs left to place in N lands. Naively, I could check all N permutations, store the valid ones, choose one at random, and I'm done. Of course, there are N! permutations, and I start out with N = 60, so this would take an impossible amount of computation and memory.