Efficiently storing all permutations of 8 different numbers and 8 zeros – Artificial Intelligence

The article is not very explicit, but the technique is reasonably clear. The two disjoint databases consist of all positions of 7 and 8 tiles (respectively) associated with a small integer. Since all positions are stored, it is not necessary to actually store a key in the database. It is sufficient to be able to compute the index of a particular key in the universe of all keys. Then a “database” is simply a vector of small integers, whose size is the total number of possible keys (16!/9! and 16!/8!, respectively). The key is not stored at all, since it is implicit.

The value stored in the database will always fit in a byte (apparently) but later in the paper there is a suggestion for ways to reduce the maximum magnitude of the datum. If you could reduce the maximum value to 15, for example, you could store two entries in a single byte, reducing the size of the database by a factor of 2.

Here’s a reasonably fast algorithm for producing a unique index for a given permutation of a k-subset of values in [0, n). The index it generates is not based on the lexicographical ordering of the permutation, but rather on the generation of the permutation using the Fisher-Yates shuffle algorithm.

The FY shuffle produces a uniformly-distributed random permutation of its input vector; it can be modified to produce a uniformly-distributed random permutation of a k-subset of its input vector by simply stopping the shuffle after k steps and truncating the output to k elements. (Stopping the shuffle early is “just” an optimization.)

A FY shuffle requires a sequence of random numbers: rnd(n), rnd(n-1), ..., rnd(1), where rnd(x) produces a uniformly-distributed random number in the range (0, x]. Each distinct sequence generates a distinct permutatation, so the permutations can be enumerated by enumerating the possible sequences. A given sequence can be mapped onto a unique integer using the factorial base system.

Again, we enumerate k-length permutations by truncating to length-k numbers; instead of using the n weights n!, (n-1)!, …, 1!, we use the first k weights n! … (n-k+1)!, renormalizing by dividing each weight by (n - k + 1)!. In practice, no division is necessary because the number is computed using Horner’s method, so that the index corresponding to d₀, d₁, …, d_k-1 is computed as:

(…((d0*n + d1)*(n-1) + d2)*(n-2) + …) + dk-1

To deduce the index from a permutation, we need to deduce the sequence for the FY algorithms by observing where each value in the permutation ends up. The code below is based on a left-to-right FY, which is the opposite of the algorithm in the linked Wikipedia article. (Left-to-right makes truncating the result easier.) So the algorithm to generate a random permutation would be:

Shuffle(n, k):
  Create Vec[n] with initial values 0,1,...,n-1
  for i from 0 to k-1:
    generate random j in the range [i, n-1]
    swap Vec[i], Vec[j]
  Result is the first k elements of Vec.

The important feature of that algorithm is that step i definitely produces the final value of Vec[i]; subsequent steps will not change Vec[i]. So to reverse the algorithm, we can deduce the value of j at step i by finding where the value at Vec[i] was at the previous step. That’s easy to do if we also track the location for each value.

Here’s the actual code, in C99, which might be easier to follow than the above explanation:

// Input: v is an array of k unique elements, each in the
//        range [0, n)
// Output: The index of v in the set of all possible such vectors.
int permindex(int n, int k, int* v) {
  int val[n], pos[n];
  // This initialization would probably have been better as
  //   for (int i = 0; i < n; ++i) val[i] = pos[i] = i;
  // The "optimization" below is intended to show that this
  // entire operation is O(k) rather than O(n); it involves
  // only initializing elements in the val and pos arrays which 
  // we might actually reference.
  for (int i = 0; i < k; ++i) {
    val[i] = i;
    pos[v[i]] = v[i];
  }
  int index = 0;
  for (int i = 0; i < k; ++i) {
    int loc = pos[v[i]]; 
    index *= n - i;
    index += loc - i;
    pos[val[i]] = loc;
    val[loc] = val[i];
  }
  return index;
}