TIL: Algorithm for Random Numbers that sum to a value.

So I was on Reddit today, and someone had posted in the learning python subreddit about his random number function was running slow…

Specifically, he was creating a list of 9 random numbers between 0 and 100 (inclusive) where the sum of those 9 numbers totaled 100. I’ve never had a situation that called for that before, and the code he gave was a simple while statement saying that while the sum of the list didn’t equal 100, empty the list, and generate 9 numbers between 0 and 100 and add them to the list, and keep going until you got a total of 100…

So I commented that of course that would take ages, as the loop probably had to run tens of thousands of times to randomly get 9 different numbers between 0 and 100 whose sum totaled 100.

My original suggestion had been to get your first number, then generate a second number between 0 and 100 – first number, and then keep doing that…

When someone else posted the following quite elegant solution… I asked where he learned it from, and he couldn’t remember where, but after further investigating, its one of those quaint mathematical formulae that always works!!!

So, in our example, we need 9 numbers between 0 and 100 (inclusive), so we take 0, and 100, and then 8 random numbers between 0 and 100, and then sort them all, so we end up with 0, 8 numbers from smallest to largest, 100…

Then you simply take the difference between each set…

So for example, let’s say our 8 random numbers were 85, 24, 58, 5, 31, 46, 94, and 7. We then take those 8 numbers, add 0 and 100 as well, and then sort them, giving us:
[0, 5, 7, 24, 31, 46, 58, 85, 94, 100]

We then simply calculate the difference between each number (5-0, 7-5, 24-7, 31-24, etc) which, by doing so would give us:
[5, 2, 17, 7, 15, 12, 27, 9, 6]

Which, in turn, sum up to 100!!

I was like… HOLY CRAP!!! I’m keeping that one in my back pocket!!!

Never B Flat, Sometimes B Sharp, Always B Natural