CombinatoricsUtil.js

'use strict';

// Authored 2018-10-26 Chase Colman
var Util = (function() {
  /**
   * combinate visitor callback
   * @callback Util~combinateCallback
   * @param {[]} combination - currently visited combination
   * @return {boolean} - terminates combinate if true
   */

  /**
   * Visits all the combinations
   * @param {[]} array - array to calculate non-repeating combinations
   * @param {number} n - size of combination set
   * @param {number} depth - recursive call depth
   * @param {number} start - start index of array
   * @param {number} end - end index of array
   * @param {Util~combinateCallback} visitor - combinate visitor callback
   * @param {?[]} combination - combination array
   */
  function combinate(array, n, depth, start, end, visitor, combination) {
    // First run
    if (combination == null) {
      combination = [];
    }

    // Visit every unique set of size n
    for (var i = start; i <= (end - n) + depth + 1; i++) {
      combination[depth] = array[i];

      if (depth < n - 1)  {
        combinate(array, n, depth + 1, i + 1, end, visitor, combination);
      } else {
        // Reached size n
        if (visitor(combination.slice())) return; // Terminate if visitor is true
      }
    }
  }

  /** @namespace */
  var Util = {
    /**
     * @param {[]} array
     * @param {number*} n - size of permutations
     * @param {number} start 
     * @param {number} end 
     * @return {[]} n-sized combinations of array[start..end]
     */
    combinateArray: function(array, n, start, end) {
      var result = [];
      combinate(array, n, 0, start, end, function(combination) {
        result.push(combination);
        return false;
      });
      return result;
    },

    /**
     * @param {[]} array
     * @param {number*} n - size of permutations
     * @param {number} start 
     * @param {number} end 
     * @param {Util~combinateCallback} visitor 
     * @return {boolean} Returns true if some combination is satisfied with visitor, false otherwise
     */
    someCombination: function(array, n, start, end, visitor) {
      var result = false;
      combinate(array, n, 0, start, end, function(combination) {
        return result = (result || visitor(combination));
      });
      return result;
    },

    /**
     * Generate a random integer between 0 and max
     * @param {number} max - maximum integer value
     */
    randomInteger: function(max) {
      return Math.floor(Math.random() * Math.floor(max));
    }
  }

  // Export Util
  return Util;
})();