A Method for Producing a Uniform Shuffle with Dice

I ran across this problem as I was reading Root: The Roleplaying Game. The game takes place in The Woodland, which is made up of twelve clearings (i.e. towns). The game comes with a few different Woodland maps you can use as is, but there is also a method for procedurally generating your own unique Woodland. A couple of these steps require rolling to randomly pick values off a list. This is fairly standard in RPGs, but here there are uniqueness constraints where you have to reroll if you get a value twice, which begins to get annoying as you exhaust values. I thought, there has to be a better way.

In computer programs, the usual way of doing this would be to shuffle your list, and pick the first however many items. A lot of languages will have a library method you can call, and if not, the algorithm for a uniform shuffle is not complicated. But, I was using paper, pencil, and dice. Could I figure out a good method for a uniform shuffle using those tools?

The Method

Start by listing your items, in any order.

A
B
C
D
E
F
G

Next, roll a die for each item on the list and write down the result.

A    3
B    1
C    5
D    3
E    3
F    1
G    2

Continue this process until you have generated a unique number for each item on the list.

A    345
B    165
C    551
D    326
E    323
F    111
G    214

You can now sort the list using these randomly generated numbers, and you'll have a randomly shuffled list.

F    111
B    165
G    214
E    323
D    326
A    345
C    551

For a slightly more efficient method, you can continue to only generate digits for items on the list that have the same value. In the above example the generated numbers might look like this instead.

A    34
B    16
C    5
D    326
E    323
F    11
G    2

From here, you can sort lexicographically by the generated numbers.

Analysis

I've done some very basic Monte Carlo simulations, and if your goal is to shuffle a list, this method does seem to require fewer rolls than the naive method of rerolling. However, the improved efficiency is small-ish. To make things easy on myself, I simulated shuffling a 20 item list using a 20 sided die. The break even point, where it was more efficient to reroll was around 17. That is, if you're selecting fewer than 17 items off the list, you're likely better off selecting and rerolling, rather than shuffling the whole list.

Another drawback is that it becomes unwieldy if the list is too long. In the case of Root, the largest table you would need to sort is a list of eighteen town names. Sorting a typical table of one hundred items would be pretty tedious. However, this can be mitigated a bit by rolling a large number of dice at the same time.

So, while the utility of this method is somewhat limited, it does still have some nice properties. This should give you a statistically uniform random shuffle, where all permutations are equally likely to occur. Off the top of my head, it should even give you a statistically random shuffle if your dice are biased in some way. Another very nice property is that it works with any size list, and any size die.

In conclusion, all I really did here was nerd snipe myself with a fun little problem.