# Algorithm for random weighted boolean shuffles?

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.

• sigh Two downvotes already.. What have I done wrong? – kangalioo Nov 2 at 17:28
• Seems like the weights are independent; if so, then weight of 3 means that the relative weights for True and False are 3 and 1 (respectively), so the absolute weighs are 3/4 and 1/4; one way to do it to call `random()` to obtain a value from the [0.0, 1.0) range, and then check if the result is < 3/4 - or, more generally, you can do something like this `[random.random() < w/(w+1) for w in weights]`, where `weights` is your list of weights. P.S. Don't take the downvotes too personally, it's just a feedback mechanism, it will go up and down. – Filip Milovanović Nov 2 at 22:23
• I vaguely recall seeing a nearly identical question with an answer indicating the desired behavior was mathematically impossible – whatsisname Nov 2 at 23:40
• If I understood the problem correctly (weighted selection from a 2-element set for each slot independently), that's not mathematically impossible; I've tried the comprehension above, it works fine (and it also works with non-integer weights). – Filip Milovanović Nov 3 at 2:35
• Oooh, sorry, I only now noticed that the True/False ratio is fixed; in that case @whatsisname may be right, as this constrains the set of possible lists. – Filip Milovanović Nov 3 at 4:49

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.

• That is really smart. I'm writing a script right now to see if the outcome looks good. – kangalioo Nov 3 at 7:57
• Seems to work fine :) Here is the function I made in Python: pastebin.com/AWHf8TLj Note that instead of True and False I used 1 and 0 – kangalioo Nov 3 at 10:39
• Nice. Heh, I didn't even notice the python tag but you seem to have translated my ramblings correctly. `random.choices` was a good call. – candied_orange Nov 3 at 14:20

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.

• +1 for the pointing out the overconstraint in the example. I had a weird feeling regarding one of my proposed approach and now I can put a word on it :-) – Christophe Nov 3 at 9:50
• Thank you for your feedback regarding the question. In my opinion what I mean with weights is already reasonably clear, though you're right that I did not explicitly specify. I will edit my question to add a clarification. (The answer I accepted is already exactly what I've been looking for by the way. The clarification of my post will be for completeness) – kangalioo Nov 3 at 10:16

## 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.

• Do you mean uniform distribution (all outcomes have equal probability)? – Filip Milovanović Nov 3 at 2:29
• @FilipMilovanović Yes ! uniform ! not normal ! thanks for pointing out this confusion :-) edited ! – Christophe Nov 3 at 9:08