<?php
/**
 * @file
 *   Script that calculates all unique combinations of a given set of elements.
 *   This script finds all combinations, not all permutations (i.e. each
 *   combination is unique regardless of the ordering of its elements).
 *
 *   Author: Jeremy Epstein
 *   Date: 16 Oct 2008
 *   License: GNU General Public License v2
 *   http://www.gnu.org/licenses/gpl-2.0.txt
 */

main();

/**
 * Main routine.
 */
function main() {
  $elements = array(
    'A',
    'B',
    'C',
    'D',
    'E',
    'F',
  );

  print_header();

  $comb_totals = find_comb_totals(count($elements));
  print_comb_totals($comb_totals);

  $combs = find_all_combinations($elements);
  print_combinations($combs);

  print_footer();
}

/**
 * Calculates the total number of possible combinations for a given number of
 * elements, for each possible group size that an element set of that size can
 * have.
 *
 * Total possible combinations is computed using the algorithm:
 *             n!
 * n_C_k = ----------
 *         k!(n - k)!
 * where n is the number of elements, and k is the group size. The possible
 * group sizes are in the range 1..n.
 *
 * @param $num_elements
 *   Number of elements in the set.
 *
 * @return
 *   Array of totals. For each element, the key is s-1, and the value is the
 *   total, where s is a possible group size.
 */
function find_comb_totals($num_elements) {
  $comb_totals = array();

  for($group_size = 1; $group_size <= $num_elements; $group_size++) {
    $comb_totals[] = factorial($num_elements) / (factorial($group_size) * factorial($num_elements - $group_size));
  }

  return $comb_totals;
}

/**
 * Finds all possible combinations of the given elements, using all possible
 * group sizes.
 *
 * @param $elements
 *   Array of elements.
 *
 * @return
 *   Array of combinations. Each combination contains its elements in
 *   comma-delimited form.
 */
function find_all_combinations($elements) {
  $combs = array();

  for($group_size = 1; $group_size <= count($elements); $group_size++) {
    find_combinations($combs, $elements, $group_size);
  }

  return $combs;
}

/**
 * Finds all possible combinations of the given elements, for the specified
 * group size.
 *
 * This function recurses ($group_size - 1) levels deep. Think of this
 * function as using a series of "pointers". Each pointer references an element
 * in the list. At maximum recursion, the number of pointers is equal to the
 * group size. Thus, at the deepest level, all the pointers together form a
 * unique combination of elements.
 *
 * E.g. with 5 elements, and a group size of 3, the pointers would begin thus:
 *   [A]  [B]  [C]  [D]  [E]
 *    ^    ^    ^
 *    1    2    3
 *
 * Then, pointer 3 would make its way towards the end:
 *   [A]  [B]  [C]  [D]  [E]
 *    ^    ^         ^
 *    1    2         3
 *
 * Once it reached the end, pointer 2 would advance by one element, and pointer
 * 3 would begin again from in front of it:
 *   [A]  [B]  [C]  [D]  [E]
 *    ^         ^    ^
 *    1         2    3
 *
 * Eventually, pointer 1 would also advance, and pointers 2 and 3 would in turn
 * begin again from in front of it:
 *   [A]  [B]  [C]  [D]  [E]
 *         ^    ^         ^
 *         1    2         3
 *
 * The final position of the pointers would be this:
 *   [A]  [B]  [C]  [D]  [E]
 *              ^    ^    ^
 *              1    2    3
 *
 * @param &$combs
 *   Array of combinations. This is passed back by reference.
 * @param $elements
 *   Array of elements.
 * @param $group_size
 *   The current number of elements in each combination.
 * @param $recurse_level
 *   Internal.
 * @param $start_index
 *   Internal.
 * @param $curr_element
 *   Internal.
 */
function find_combinations(&$combs, $elements, $group_size, $recurse_level = 1, $start_index = 0, $curr_element = '') {
  // This is the start of a new recursion level, so set the starting position
  // of our newest pointer.
  $element_index = $start_index;

  do {
    // Work out the current combination, by concatenating the elements pointed
    // to by pointers higher in the recursion stack, with the elements targeted
    // by the current pointer.
    $new_comb = $curr_element;
    if (!empty($new_comb)) {
      $new_comb .= ',';
    }
    $new_comb .= $elements[$element_index];


    if ($recurse_level == $group_size) {
      // If we're at maximum recursion, then we have a complete combination, so
      // add it to the list.
      $combs[$new_comb] = $new_comb;
    }
    else {
      // The current combination is less than the group size, so recurse one
      // level deeper, giving the next recursion level's pointer a starting
      // index one place ahead of the current pointer's position.
      find_combinations($combs, $elements, $group_size, $recurse_level + 1, $element_index + 1, $new_comb);
    }

    // This is the current pointer, and it's unique at each recursion level.
    $element_index++;

    // Each level down, we allow our pointer to go one spot further, until the
    // pointer at maximum recursion reaches the end of the list.
  } while ($element_index < count($elements) - $group_size + $recurse_level);
}

/**
 * Recursively calculates the factorial of a number (i.e. n!).
 *
 * @param $number
 *   Input number.
 *
 * @return
 *   Factorial of the number.
 */
function factorial($number) {
  if ($number == 0) return 1;
  return $number * factorial($number - 1);
}

/**
 * Prints a page header.
 */
function print_header() {
  print "<html>\n";
  print "<head>\n";
  print "  <title>Combination algorithm</title>\n";
  print "</head>\n\n";
  print "<body>\n\n";
  print "<h1>Combination algorithm</h1>\n\n";
}

/**
 * Prints a table of combination totals.
 */
function print_comb_totals($comb_totals) {
  $grand_total = 0;
  print "<h2>Totals:</h1>\n\n";
  print "<table border=\"1\" style=\"font-family: Courier New\">\n";
  print "  <tr><th>Group size</th><th>Total combinations</th></tr>\n";

  foreach ($comb_totals as $index => $comb_total) {
    print "  <tr><td>". ($index + 1) ."</td><td align=\"right\"><pre>". str_pad($comb_total, 5, ' ', STR_PAD_LEFT) ."</pre></td></tr>\n";
    $grand_total += $comb_total;
  }
  print "  <tr><th>Grand total:</th><th align=\"right\"><pre>". str_pad($grand_total, 5, ' ', STR_PAD_LEFT) ."</pre></th></tr>\n";

  print "</table>\n\n";
}

/**
 * Prints a list of possible combinations.
 */
function print_combinations($combs) {
  print "<h2>Combinations:</h1>\n\n";
  print "<ol>\n";

  foreach ($combs as $comb) {
    print "  <li>". $comb ."</li>\n";
  }

  print "</ol>\n\n";
}

/**
 * Prints a page footer.
 */
function print_footer() {
  print "</body>\n";
  print "</html>\n";
}