randomizers and bias (1/N)
So for the randomizer, I wanted to add a mode ("full") that assigns orbs to lands as close to 1:1 as possible. Some pairings of orbs/lands are not allowed, and there are a lot of special cases in this logic. I wanted to place them such that they are unbiased, i.e. every possible placement has equal probability. That is surprisingly difficult.
randomizers and bias (2/N)
The naive algorithm would be to shuffle the orbs completely at random. If this results in an invalid configuration, try again until it works. That would be unbiased, but in this case, certain lands and orbs accept only a few pairings, so there'd be a lot of retries.
randomizers and bias (3/N)
One could adjust that by checking pairs during the process and rerolling any invalid pairs. However, this would introduce bias. Early on, each pairing is equally likely, but these pairings eliminate different numbers of possibilities later. If I place a more "restricted" orb that can go in only a few lands, that eliminates relatively few possibilities for it, compared to other orbs that could go anywhere.
randomizers and bias (4/N)
And this algorithm can still hit dead ends, if an orb or land has no valid pairings left.
randomizers and bias (5/N)
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.
randomizers and bias (6/N)
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.
randomizers and bias (7/N)
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.
randomizers and bias (8/N)
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.
randomizers and bias (9/N)
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.
randomizers and bias (10/N)
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.
randomizers and bias (11/N)
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.
randomizers and bias (12/N)
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.
randomizers and bias (14/N)
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.
randomizers and bias, bad end (15/N)
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.
randomizers and bias, bad end (15/N)
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.
randomizers and bias, bad end
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.
randomizers and bias (13/N)
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.