Last time on FAIC I showed how you could produce the mth permutation of n elements, where m is a number between zero and n!-1 that chooses from the n! possible permutations. There’s a very interesting way to represent numbers that are always less than n! for a given n that I thought I might talk about today.

First off, a quick refresher on how we represent numbers textually in the first place. A four-digit number in base ten, say 2345, is nothing more than a compact way of writing

2 x 103 + 3 x 102 + 4 x 101 + 5 x 100

If we wanted to write that number in a different base, we could. For example, that quantity in base eight is:

4 x 83 + 4 x 82 + 5 x 81 + 1 x 80

So in base eight that would be 4451₈. (Conventionally the subscript indicates the base; base 10 is assumed if not present.)

There’s a fundamental rule here that often goes unmentioned because it is obvious: the digits must be smaller than the base. An equally obvious property is that every digit smaller than the base must be legal; otherwise we end up in the opposite situation of having some integers with no representation in the notation. If we allowed the digits 0 through 9 in numbers written in base eight then we would be in the unfortunate situation that 9₈ == 11₈. We want the representation of a given integer to be unique. By requiring that each digit be smaller than the base, we obtain the property that the largest number with n digits is one smaller than the smallest number with n+1 digits; 999 is one less than 1000, 777₈ is one less than 1000₈, and so on. Proving this fact for arbitrary base is left as an exercise.

Hold onto your butts because now is the bit where things get a bit weird. Who says that the “base” has to be the same for every digit? Who says each digit has to be multiplied by a power? We can instead say that the nth digit is between zero and n, and multiplied by n!:

234510 = 3 x 6! + 1 x 5! + 2 x 4! + 2 x 3! + 2 x 2! + 1 x 1! + 0 x 0!

That is, we can write the decimal number 2345 in factoradic notation as 3122210_!. This is simply another way of uniquely notating every integer. Opinions vary as to whether you should put the final digit zero on there; since it cannot be anything other than zero it seems redundant. However I’ll stick with it for the purposes of this blog post.

Just as any integer between zero and 10ⁿ-1 can be represented by n decimal digits, any integer between zero and n!-1 can be uniquely represented by n factoradic digits. And notice that the property I mentioned before holds: 43210_! is one less than 100000_!.

Suppose we wanted to generate a random BigInteger between zero and n!-1. All we need to do is generate the n digits of a number in factoradic notation, and we’re set:

// Produce a random number between 0 and n!-1
static BigInteger RandomFactoradic(int n, Random random)
{
  BigInteger result = 0;
  BigInteger radix = 1;
  for (int i = 1; i < n; ++i)
  {
    // We need a digit between 0 and i.
    result += radix * random.Next(i + 1);
    radix *= (i + 1);
  }
  return result;
}

Which means that we can generate a random permutation! Just generate a random number between 0 and n!-1, that gives you back a BigInteger, and you can feed that into the permutation generator we made last time. Awesome.

Hold on just a minute here. Something about this is looking really familiar. Where have I seen this technique for generating a random permutation before?

static void FischerYatesShuffle(T[] array, Random random)
{
  for (int i = array.Length - 1; i > 0; i -= 1)
  {
    int item = random.Next(i + 1);
    T temp = array[i];
    array[i] = array[item];
    array[item] = temp;
  }
}

This is the standard algorithm for uniformly shuffling an array, and it also chooses a sequence of random numbers n or less, n-1 or less, and so on, to produce a random permutation. And in fact that’s how we deduced that there were n! permutations in the first place: you choose from n items the first time, n-1 items the second time, and so on. So really the algorithm I came up with today is in a sense equivalent to the Fischer-Yates shuffle; both shuffles choose a sequence of numbers that could be digits in a factoradic representation of an integer less than n! and use that to produce a permutation. Precisely which permutation they choose based on a given sequence is of course different, but ultimately they are doing the same thing: choosing an ordering for all the permutations and then picking one out based on an index into that ordering.

Next time on FAIC: I see my picture on the cover of a magazine. Then we’ll resume this series, with the observation that these implementations lack certain properties that you might want in a high-grade shuffle. We’ll explore those properties.