Suppose you want to draw randomly a number between 0 and 1, with multiple throws of a six sided dice, what would you write down on its face?
If you want to form numbers between 0 (inclusive) and 1 (exclusive), you could assign the faces a subset of the usual digits (0 to 9), and throw the dice multiple time, each time giving you a new decimal. So throwing 3, 4, 7, 8, (say) would give you 0.3478. But how do we chose what to write on the faces?
Intuitively, we would think that spacing the digits as evenly as possible is the way to go, something like 1, 3, 5, 7, 8, 9. But is our intuition correct? There are subsets of six digits, so there’s not that many to check, so we can use brute force enumeration. But how do we measure the evenness of the spread of generated numbers? We simply measure the (square of the) distance between all possible numbers generated.
The test therefore relies on three steps. 1) generate all possible subsets, 2) generate all possible numbers we can represent with the digits from each of the subsets, and 3) measure distance.
The first step, generate all possible subsets, can be done using the “shuttle algorithm” that takes a permutation of (not necessarily distinct symbols) and yield the next one in lexicographical order. We’ve already met this algorithm in a previous entry. We start with the initial permutation 0,0,0,0,1,1,1,1,1,1. The next will be 0,0,0,1,0,1,1,1,1,1. Eventually, we reach the last one, 1,1,1,1,1,1,0,0,0,0. We use the permutation as a bit-vector to select the subset of digits: 0,1,1,0,0,0,1,1,1,1 selects 1,2,6,7,8,9 from 0,1,2,…,9.
The second step is done with a base six counter, that will count, on a fix length, from 0 to n-digit overflow. This counters goes 0, 1, 2, 4, 5, 10, 11, 12, 13, 15, 25,… A presentation layer converts the number represented by the counter to the actual symbols from the subset. That re-coded number is converted to a float (or an integer).
The third, and last, step, just measures the spacing between successive numbers. This means that a number that goes from xxxx15 to xxxx20 will incur a larger penalty than a number that goes from yyyy18 to yyyy20.
Running the program will let us discover the best subset of digits to write on the dice’s faces:
024689 425723808 135789 520243666 146789 733009458 246789 827529316 256789 1040295108 345678 1339694288 356789 1347580758 456789 2080397992
So for this almost kind-of ten-sided dice on a six-side dice, the best combination is 0, 2, 4, 6, 8, 9. It’s not the only one. The program only selects a new combination if it has a strictly better score than the previous one. But we also find 0,1,2,3,5,7,9, 0,2,3,5,7,9, 0,2,4,5,7,9, and 0,2,4,6,7,9 with the same discrepancy, or, alternatively, with the same evenness.