365 DoC - W1, D1 - Subset Permutations

Problem: based on a given finite set of elements, find every possible combination of X elements, where X indicates 1 to X.

Example: in the finite set of elements (A, B, C), all possible combinations of up to three elements would be ((A), (B), (C), (A, B), (A, C), (B, C), (A, B, C)) - this assumes that we would treat (A, B) and (B, A) as the same permutation of a 2-element subset, etc.

Solution: if you think of the set of elements as digits in a number system, then you simply need to enumerate between 'zero' and the max for the number of elements in each permutation, while eliminating duplicates. For example, decimal (base-10) is a number system comprised of a set of 10 possible elements: the digits 0 through 9. So, given this set, if we wanted to find all the permutations of up to 3 elements, we simply count from 0 to 999, and eliminate duplicates/repeats, ie: '999' would be eliminated because we would already have '9' in the list of possible permutations... likewise, '21' would be omitted, since at that point we'd already have '12' in the set of possible permutations of digit combinations ('21' is just a re-arrangement of the digits in '12').

Sounds complicated, but we really just need two things: a function to 'increment' a set of elements (the permutation), and an easy/efficient way to check for duplicates/repetitions.

The first item will end up being a simple implementation of an elementary school place-value lesson... the pseudo-code will look something like this:

possible elements: A, B, C
permutation to 'increment': (A, C)

- set the current 'place' we're working on to zero (the first 'digit', 'C' in this case if we're working right-to-left)
- is the 'value' of the element at the current place the last possible value in the set of possible elements?
yes: set the value of the current place to the first element in the set, move the place up one, and repeat
no: set the value of the current place to the next element in the set

'A, C' would be "incremented" to 'B, A'

This is a actually a good candidate for recursion, although I didn't really plan on talking about recursion in today's excercise... here's a simple implementation of the above 'algorithm' in PHP...

$possibleElements = array('A', 'B', 'C');

function incrementPermutation(&$perm, $place = 0)
{
  global $possibleElements;

  if ( !isset($perm[$place]) )
    $perm[$place] = $possibleElements[0];
  else {
    $valueIndex = array_search($perm[$place], $possibleElements) + 1;

    if ( $valueIndex < count($possibleElements) )
      $perm[$place] = $possibleElements[$valueIndex];
    else {
      $perm[$place] = $possibleElements[0];

      $place ++;

      incrementPermutation($perm, $place);
    }
  }
}

The implementation is slightly incomplete - there's not argument checking (the $perms parameter needs to be an array), no checking of the $possibleElements array, and there's some other updates we could make so it's more general-purpose, but it will work as-is. PHP might optimize it out anyways, but for the sake of writing good code we've kept the $possibleElements declaration/initialization outside of the function body so that it's not re-declared every time we (potentially) recurse.

Instead of commenting the function to explain it's operation, let's dissect it piece by piece:

$possibleElements = array('A', 'B', 'C');

This is just setting up an array to hold the full set of elements from which we'll be generating permutations - if we were working with a real numbering system, this would hold our digits, in order... ie: array('0', '1', ..., '9');

function incrementPermutation(&$perm, $place = 0)
{
  global $possibleElements;

Our function declaration... we're passing $perm, which is an array representing the existing permutation to increment, by reference so we don't need to write clumsy $var = func($var) type statements all over. $place defaults to zero so that outside of the recursive calls, ie: elsewhere in our code, we just call incrementPermutation($perm) without worrying about explicitly telling the function to start at the "least-significant" spot in the permutation.

Again using the example of a numbering system, $place indicates the place-position in the number that we're working with. This corresponds to the 'ones' or 'tens' or 'hundreds' position in a decimal numbering system, if you remember back to the explanation you got in grade school.

if ( !isset($perm[$place]) )
    $perm[$place] = $possibleElements[0];

First we check if the $place we're working with has already been set/defined... if not, incrementing is easy: we just set it to the first element in $possibleElements and we're done.

else {
    $valueIndex = array_search($perm[$place], $possibleElements) + 1;

Otherwise, we'll need to do some real work - first we need to figure out where in the set of possible elements the current value of the element at $place in our permutation resides. We increment that because in both places where we're about to use it we need to increment it anyways, so we might as well do that right off the bat...

if ( $valueIndex < count($possibleElements) )
      $perm[$place] = $possibleElements[$valueIndex];

This expression, if True, indicates that we don't need to "carry-over" anything - we can increment the value at the current place without running out of elements in the original set to use. $valueIndex represents the next possible index/key in the array of possible elements. If it's not less than the size of $possibleElements, that means we're already at the last possible element and need to 'carry-over'. Otherwise, it will 'point' to the next possible element, which is used as the incremented value for this $place in our permutation.

else {
      $perm[$place] = $possibleElements[0];

      $place ++;

      incrementPermutation($perm, $place);
    }

If we do have to carry-over a value, we set the current place's value to the first in the set of possible elements, increment the $place variable, and recurse, passing in the new value of $place, in order to perform the whole increment operation on the next place over.

Next, we need to deal with the task of identifying duplicates/repetitions in our permutations. The solution is relatively simple... we're going to write a function that generates a numerical value for our resulting permutation, based on a bitmask that assigns a different (bit-)value to each possible element in our original set. To generate the value of our permutation, we perform a bitwise OR on the bits corresponding to each 'digit' in the permutation, and then obtain the resulting decimal representation of the number. If this matches the value of a permutation already in our 'found permutations' array, which we're tracking, then we can safely ignore it.

Here's the function:

function permutationValue($perm)
{
    global $possibleElements;

    $value = 0;

    foreach ( $perm as $element )
        $value |= 1 << array_search($element, $possibleElements);

    return $value;
}

It's pretty simple - we're just finding the position (index) of each element in our permutation, and using that as a bitshift operand in our |= operation, which 'adds' bits to $value.

And that's pretty much it - using these two functions, we can enumerate all possible combinations of the elements in a given, arbitrary set, and by keeping track of our permutation 'values', we can check for duplicates/repetition before adding each found permutation to the final list (array) of permutations discovered.

Here's the complete version of the code, with a built-in example... you can see the output here.

// define the members of the entire set
$possibleElements = array('A', 'B', 'C');

// the max size of a permutation is the number of elements in the original set
$maxSetSize = count($possibleElements);

// initialize an array to store the found permutations
$permutations = array();

// initialize an array to store the "values" of each permutation found
$permutationValues = array();

// determine the "value" of a permutation
function permutationValue($perm)
{
    global $possibleElements;

    $value = 0;

    foreach ( $perm as $element )
                    $value |= (1 << array_search($element, $possibleElements));

    return $value;
}

// "increment" a permutation, using each element of the original/whole set as a possible "digit"
// in our arbitrary number system
function incrementPermutation(&$perm, $place = 0)
{
  global $possibleElements;

  if ( !isset($perm[$place]) )
    $perm[$place] = $possibleElements[0];
  else {
    $valueIndex = array_search($perm[$place], $possibleElements) + 1;

    if ( $valueIndex < count($possibleElements) )
      $perm[$place] = $possibleElements[$valueIndex];
    else {
      $perm[$place] = $possibleElements[0];

      $place ++;

      incrementPermutation($perm, $place);
    }
  }
}

$currentPerm = array();

while ( count($currentPerm) <= $maxSetSize ) {
  // "increment" the current permutation
  incrementPermutation($currentPerm);

  // calculate the value of the new permutation
  $currentPermValue = permutationValue($currentPerm);

  // if it's not already in our array of values, add the new
  // permutation to the list of ones we've found
  if ( FALSE === array_search($currentPermValue, $permutationValues)) {
    array_push($permutations, $currentPerm);
    array_push($permutationValues, $currentPermValue);
  }
}

// Dump out the final list of permutations in semi-pretty/human-readable format
print_r($permutations);