Permutations and Combinations with Ruby’s Array

So I’ve been having fun resurrecting code from my past to help me with the work I’m doing today, which is pretty awesome.

But you know what’s even more Aweseome? Ruby’s Array class. It’s gotten two new methods since 1.8.6 that do some nifty, mathy things: #permutation and #combination.

Permutations and combintations are both ways of constructing sets from a single group of primitives. You may remember something along the lines of “N choose K”.

From N items, you can choose K of those items. If order matters in the groups you are making then you are choosing permutations. If order does not matter, then you are choosing combinations. In cases larger than 1, there will always be more permutations than combinations.

The formula for permutations is as follows:

permutations

However, I’ve always found the easiest way to think of permutations in terms of an empty array that you’re filling with elements:

                   

Let’s take the full example of having 10 items and wanting permutations that have a size of 10. So we’d say this is “10 choose 10”, initializing our variables N and K to 10. When we go to fill up the first spot in the array, we have all 10 items to pick from.

1 of 10                  

Now when we go to fill up the second spot, we one have 9 elements to choose from, so we’re picking 1 from the 9 remaining.

1 of 10 1 of 9                

To tally the grand total number of choices I can simply multiply 10 x 9 to arrive at 90. That is because choosing 2 then 1 is different from choosing 1 then 2, and it actually makes the math easier. This process continues:

1 of 10 1 of 9 1 of 8 1 of 7 1 of 6 1 of 5 1 of 4 1 of 3 1 of 2 1 of 1

As you can see, you just keep multiplying N by N-1. This is why, for the special case where N=k, the total number of permutations is N!, or N factorial. For any cases smaller than that, you wind up with “just the head” of the factorial bit. For example, in 10 choose 4 you are only doing the following:

1 of 10 1 of 9 1 of 8 1 of 7            

For me, the trick to understanding the formula is realizing what it is doing in the denominator is cancelling out the tail of 6 x 5 x 4 x 3… We know to start at six either by making my table above or using the formula to calulate N-K, which in this case is 10-4 = 6.

Combinations are like permutations, but order doesn’t matter. The formula is very similar:

combinations

In fact, you can think of this as being the same process as permutations, but needing that k! in the denominator to cancel out subsets that already exist.

If you’re going to be using permutations and combinations in your code, its important to be able to calculate the size without needing to generate all the options because it can quickly overwhelm your computer.

Back of the envelope:

210 = 1024
10! = 3,628,800

2100 = 1.2 x 1030
100! = 9.3 x 10157

That said, let’s take a look at how Ruby makes using permutations and combintations in your code deceptively simple:

Array#permutation

   a = [1, 2, 3]
   a.permutation.to_a
      [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   a.permutation(1).to_a
      [[1],[2],[3]]
   a.permutation(2).to_a
      [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
   a.permutation(3).to_a
      [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   a.permutation(0).to_a
    [[]] # one permutation of length 0
   a.permutation(4).to_a
    []   # no permutations of length 4

Array#combination

  a = [1, 2, 3, 4]
  a.combination(1).to_a
    [[1],[2],[3],[4]]
  a.combination(2).to_a
    [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
  a.combination(3).to_a
    [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
  a.combination(4).to_a
    [[1,2,3,4]]
  a.combination(0).to_a
    [[]] # one combination of length 0
  a.combination(5).to_a
    []   # no combinations of length 5

For reference’s sake I’ve included the implementation of permute0, which does the permutation calculation. This is implemented in array.c of Ruby recursively. Combination, however, is generated iteratively. In large cases this can impact the performance of these two functions.

In production code, I’d say the best place to use these is not going to be in some sort of AI subsystem, but most likely with a small set where its more expressive to generate permutations/combintations instead of listing them.

Appendix A: permute0 in array.c

/*
 * Recursively compute permutations of r elements of the set [0..n-1].
 * When we have a complete permutation of array indexes, copy the values
 * at those indexes into a new array and yield that array.
 *
 * n: the size of the set
 * r: the number of elements in each permutation
 * p: the array (of size r) that we're filling in
 * index: what index we're filling in now
 * used: an array of booleans: whether a given index is already used
 * values: the Ruby array that holds the actual values to permute
 */
static void
permute0(n, r, p, index, used, values)
    long n, r, *p, index;
    int *used;
    VALUE values;
{
    long i,j;
    for (i = 0; i < n; i++) {
      if (used[i] == 0) {
          p[index] = i;
          if (index < r-1) {             /* if not done yet */
              used[i] = 1;               /* mark index used */
              permute0(n, r, p, index+1, /* recurse */
              used, values);
              used[i] = 0;               /* index unused */
          }
          else {
            /* We have a complete permutation of array indexes */
            /* Build a ruby array of the corresponding values */
            /* And yield it to the associated block */
            VALUE result = rb_ary_new2(r);
            VALUE *result_array = RARRAY(result)->ptr;
            const VALUE *values_array = RARRAY(values)->ptr;

            for (j = 0; j < r; j++) result_array[j] = values_array[p[j]];
            RARRAY(result)->len = r;
            rb_yield(result);
         }
      }
    }
}

c2

Fork me on GitHub