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.

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.

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.

And this algorithm can still hit dead ends, if an orb or land has no valid pairings left.

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.

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.

@madewokherd 🐍 ooh! how many orbs are restricted in what ways? (we remembered that we like math puzzles)