Algorithm for random weighted boolean shuffles?

Question

I don't exactly know how to phrase the thing I'm searching for in a succinct way, which also made it hard to research.

In my application I need a random list of booleans, say of length five. The number of True's and False's in the list are fixed, for example 2x True and 3x False. Generating a list of that kind is easy:

random.shuffle([True, True, False, False, False])

However, I also need some weights for the shuffling. By this I mean that I need to control - for each of the five places in the list - how likely it is that a True will be placed there.

Continuing with the example; with weights [3, 1, 1, 1, 1] the outcome [T, F, T, F, F] should be 3 times more likely than [F, T, T, F, F]. That's because the first list entry has triple the weight of the second entry, hence a True is more likely to be in first place instead of second.

Note that from this you cannot make assumptions about a single place in the list. The outcome for one individual list place also depends on the rest of the list (because the number of True's is fixed), which makes this problem so tricky for me.

I have no idea how to approach that problem and also, as I said, research is hard because I can't phrase this problem succinctly. Any help or links will be appreciated.

Answer 1

Each bool deserves to have its weight count for something even if it's set last when the true's are all used up.

Here's my approach. Pretend each bool wants to be true. Pick which one to set true next according to weight. When you run out of true, stop.

An implementation to do this could create a list of bit indexes (or masks) that repeat due to weight. Then just shuffle the list.

The tricky thing is once a bool has been set all copies of its index need to be removed from the list. Not just the one at the top.

The advantage of this approach is that all weights get influence at every step without having to calculate probabilities.

The disadvantage is that large weights are memory intensive.

A memory optimized solution would keep the weighs and bools in parallel arrays (if not structs, objects or tupples).

The key here is turning the bool on turns the weight off. It no longer counts when trying to place the next true. It no longer counts when adding up the weights to find the next range of random values to choose from.

sum = sumUnsetWeights();
rand = randInt(1, sum);
setByWeight(rand);

Loop over that as many times as you want a bool set.

Answer 2

If I understand correctly, the problem is misspecified, underspecified and most likely overconstrained.

Misspecified: Your second example of a possible outcome has 6 elements. That is contradictory to the requirement that each outcome should have 5 elements. This has been corrected, thank you!

Underspecified: You state that the weight 3 means that a boolean True is 3 times more likely in this position than a False. One might interpret that as saying that the probability of True at this position is 0.75, but that is not explicitly given.

Overconstrained: The weights as interpreted above indicate that in each position of the outcome, the probability of True is at least as high as the probability of False; actually, the average number of True elements in each outcome is 2.75 (sum of the probabilities) but as it is stated that each outcome has 2 True values this is not possible.

I think you need to refine the problem statement to better specify what your weights are supposed to mean.

Answer 3

The problem

I understand that you need to generate a fixed length list of N random booleans, that obeys a distribution rule by position and that complies with a contraint about the number of T. Quite challenging ! I'll answer assuming that you have a reliable random number generator that guarantees a uniform distribution;

First approach

The proposed idea is to create N lists, that reflect the distribution requirements of each position. In your example:

[ T, T, T, F ]
[ T, F]
[ T, F]
[ T, F]
[ T, F]

Using a random generator with uniform distribution, you would then select in each list one element. Since the distribution is uniform, each element in each list has equal number of chances to be selected. The weighting is achieved via the repetitive elements. The composed list of results would then be checked against the constraints: if doesn't fit the expected number of Ts, it's rejected. Randomness and distribution should be respected as each position is selected independently.

The drawback with this approach is that you may have to generate several candidate lists before finding one that matches the constraint regarding the number of Ts. But if you would take shortcuts, you might flaw the individual distribution of the positions. For example, puting remaing positions to F as soon as all the Ts are there, would favor an overrepresentation of Ts in the first boolean positions and an underrepresentation in the last boolean positions.

Alternative

An alternative to that approach with less waste could be to construct a shuffle-set, that contains candidate lists that respect the constraint. The shuffle set would repeat some combinations so that the distribution per position is respected. You'd then use your uniform random number generator to pick one candidate list in the set. Since each candidate has the same chance of being selected, the distribution is again obtained by repeating combinations according to the weighting.

This approach would require more memory. The difficulty is transferred to the construction of the candidate set: the main risk is that by trying to add repetitive items for the positions with the highest weight, you could distort randomness of the remaining positions (i.e. creating an unwanted correlation between some positions). This risk seems relatively high in the given example in view of the over-contraint issue raised in Hans-Martin’s answer. I nevertheless imagine that your real distributions by position are certainly more consistent than in your example.

In any case, I'd strongly suggest to create a tester that checks the distribution over a large number of generations.