text: /*
   * $Id: combinatorics.js,v 0.25 2013/03/11 15:42:14 dankogai Exp dankogai $
   *
   *  Licensed under the MIT license.
   *  http://www.opensource.org/licenses/mit-license.php
   *
   *  References:
   *    http://www.ruby-doc.org/core-2.0/Array.html#method-i-combination
   *    http://www.ruby-doc.org/core-2.0/Array.html#method-i-permutation
   *    http://en.wikipedia.org/wiki/Factorial_number_system
   */
  (function (root, factory) {
      if (typeof define === 'function' && define.amd) {
          define([], factory);
      } else if (typeof exports === 'object') {
          module.exports = factory();
      } else {
          root.Combinatorics = factory();
      }
  }(this, function () {
      'use strict';
      var version = "0.5.5";
      /* combinatory arithmetics */
      var P = function(m, n) {
          if (n % 1 !== 0) throw new RangeError;
          var p = 1;
          while (n--) p *= m--;
          return p;
      };
      var C = function(m, n) {
          if (n > m) {
              return 0;
          }
          return P(m, n) / P(n, n);
      };
      var factorial = function(n) {
          return P(n, n);
      };
      var factoradic = function(n, d) {
          var f = 1;
          if (!d) {
              for (d = 1; f < n; f *= ++d);
              if (f > n) f /= d--;
          } else {
              f = factorial(d);
          }
          var result = [0];
          for (; d; f /= d--) {
              result[d] = Math.floor(n / f);
              n %= f;
          }
          return result;
      };
      /* common methods */
      var addProperties = function(dst, src) {
          Object.keys(src).forEach(function(p) {
              Object.defineProperty(dst, p, {
                  value: src[p],
                  configurable: p == 'next'
              });
          });
      };
      var hideProperty = function(o, p) {
          Object.defineProperty(o, p, {
              writable: true
          });
      };
      var toArray = function(f) {
          var e, result = [];
          this.init();
          while (e = this.next()) result.push(f ? f(e) : e);
          this.init();
          return result;
      };
      var common = {
          toArray: toArray,
          map: toArray,
          forEach: function(f) {
              var e;
              this.init();
              while (e = this.next()) f(e);
              this.init();
          },
          filter: function(f) {
              var e, result = [];
              this.init();
              while (e = this.next()) if (f(e)) result.push(e);
              this.init();
              return result;
          },
          find: function(f) {
              var e, result;
              this.init();
              while (e = this.next()) {
                  if (f(e)) {
                      result = e;
                      break;
                  }
              }
              this.init();
              return result;
          },
          reduce: function(reducer, result) {
              // return this.toArray().reduce(reducer, init);
              this.init();
              var index = 0;
              if (arguments.length < 2) {
                  result = this.next();
                  index += 1;
              }
              var length = this.length;
              while(index < length) {
                  result = reducer(result, this.next(), index, this);
                  index += 1;
              }
              return result;
          },
          lazyMap: function(f) {
              this._lazyMap = f;
              return this;
          },
          lazyFilter: function(f) {
              Object.defineProperty(this, 'next', {
                  writable: true
              });
              if (typeof f !== 'function') {
                  this.next = this._next;
              } else {
                  if (typeof (this._next) !== 'function') {
                      this._next = this.next;
                  }
                  var _next = this._next.bind(this);
                  this.next = (function() {
                      var e;
                      while (e = _next()) {
                          if (f(e))
                              return e;
                      }
                      return e;
                  }).bind(this);
              }
              Object.defineProperty(this, 'next', {
                  writable: false
              });
              return this;
          }
  
      };
      /* power set */
      var power = function(ary, fun) {
          var size = 1 << ary.length,
              sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'index');
          addProperties(that, {
              valueOf: sizeOf,
              init: function() {
                  that.index = 0;
              },
              nth: function(n) {
                  if (n >= size) return;
                  var i = 0,
                      result = [];
                  for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              },
              next: function() {
                  return this.nth(this.index++);
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
      /* combination */
      var nextIndex = function(n) {
          var smallest = n & -n,
              ripple = n + smallest,
              new_smallest = ripple & -ripple,
              ones = ((new_smallest / smallest) >> 1) - 1;
          return ripple | ones;
      };
      var combination = function(ary, nelem, fun) {
          if (!nelem) nelem = ary.length;
          if (nelem < 1) throw new RangeError;
          if (nelem > ary.length) throw new RangeError;
          var first = (1 << nelem) - 1,
              size = C(ary.length, nelem),
              maxIndex = 1 << ary.length,
              sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'index');
          addProperties(that, {
              valueOf: sizeOf,
              init: function() {
                  this.index = first;
              },
              next: function() {
                  if (this.index >= maxIndex) return;
                  var i = 0,
                      n = this.index,
                      result = [];
                  for (; n; n >>>= 1, i++) {
                      if (n & 1) result[result.length] = this[i];
                  }
  
                  this.index = nextIndex(this.index);
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
      /* bigcombination */
      var bigNextIndex = function(n, nelem) {
  
          var result = n;
          var j = nelem;
          var i = 0;
          for (i = result.length - 1; i >= 0; i--) {
              if (result[i] == 1) {
                  j--;
              } else {
                  break;
              }
          } 
          if (j == 0) {
              // Overflow
              result[result.length] = 1;
              for (var k = result.length - 2; k >= 0; k--) {
                  result[k] = (k < nelem-1)?1:0;
              }
          } else {
              // Normal
  
              // first zero after 1
              var i1 = -1;
              var i0 = -1;
              for (var i = 0; i < result.length; i++) {
                  if (result[i] == 0 && i1 != -1) {
                      i0 = i;
                  }
                  if (result[i] == 1) {
                      i1 = i;
                  }
                  if (i0 != -1 && i1 != -1) {
                      result[i0] = 1;
                      result[i1] = 0;
                      break;
                  }
              }
  
              j = nelem;
              for (var i = result.length - 1; i >= i1; i--) {
                  if (result[i] == 1)
                      j--;
              }
              for (var i = 0; i < i1; i++) {
                  result[i] = (i < j)?1:0;
              }
          }
  
          return result;
  
      };
      var buildFirst = function(nelem) {
          var result = [];
          for (var i = 0; i < nelem; i++) {
              result[i] = 1;
          }
          result[0] = 1;
          return result;
      };
      var bigCombination = function(ary, nelem, fun) {
          if (!nelem) nelem = ary.length;
          if (nelem < 1) throw new RangeError;
          if (nelem > ary.length) throw new RangeError;
          var first = buildFirst(nelem),
              size = C(ary.length, nelem),
              maxIndex = ary.length,
              sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'index');
          addProperties(that, {
              valueOf: sizeOf,
              init: function() {
                  this.index = first.concat();
              },
              next: function() {
                  if (this.index.length > maxIndex) return;
                  var i = 0,
                      n = this.index,
                      result = [];
                  for (var j = 0; j < n.length; j++, i++) {
                      if (n[j])
                          result[result.length] = this[i];
                  }
                  bigNextIndex(this.index, nelem);
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
      /* permutation */
      var _permutation = function(ary) {
          var that = ary.slice(),
              size = factorial(that.length);
          that.index = 0;
          that.next = function() {
              if (this.index >= size) return;
              var copy = this.slice(),
                  digits = factoradic(this.index, this.length),
                  result = [],
                  i = this.length - 1;
              for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
              this.index++;
              return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
          };
          return that;
      };
      // which is really a permutation of combination
      var permutation = function(ary, nelem, fun) {
          if (!nelem) nelem = ary.length;
          if (nelem < 1) throw new RangeError;
          if (nelem > ary.length) throw new RangeError;
          var size = P(ary.length, nelem),
              sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'cmb');
          hideProperty(that, 'per');
          addProperties(that, {
              valueOf: function() {
                  return size;
              },
              init: function() {
                  /* combination can only be used for less than 31 elements */
                  if (ary.length < 31) {
                      this.cmb = combination(ary, nelem);
                  } else {
                      this.cmb = bigCombination(ary, nelem);
                  }
                  
                  this.per = _permutation(this.cmb.next());
              },
              next: function() {
                  var result = this.per.next();
                  if (!result) {
                      var cmb = this.cmb.next();
                      if (!cmb) return;
                      this.per = _permutation(cmb);
                      return this.next();
                  }
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
  
      var PC = function(m) {
          var total = 0;
          for (var n = 1; n <= m; n++) {
              var p = P(m,n);
              total += p;
          };
          return total;
      };
      // which is really a permutation of combination
      var permutationCombination = function(ary, fun) {
          // if (!nelem) nelem = ary.length;
          // if (nelem < 1) throw new RangeError;
          // if (nelem > ary.length) throw new RangeError;
          var size = PC(ary.length),
              sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'cmb');
          hideProperty(that, 'per');
          hideProperty(that, 'nelem');
          addProperties(that, {
              valueOf: function() {
                  return size;
              },
              init: function() {
                  this.nelem = 1;
                  // console.log("Starting nelem: " + this.nelem);
                  this.cmb = combination(ary, this.nelem);
                  this.per = _permutation(this.cmb.next());
              },
              next: function() {
                  var result = this.per.next();
                  if (!result) {
                      var cmb = this.cmb.next();
                      if (!cmb) {
                          this.nelem++;
                          // console.log("increment nelem: " + this.nelem + " vs " + ary.length);
                          if (this.nelem > ary.length) return;
                          this.cmb = combination(ary, this.nelem);
                          cmb = this.cmb.next();
                          if (!cmb) return;
                      }
                      this.per = _permutation(cmb);
                      return this.next();
                  }
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
      /* Cartesian Product */
      var arraySlice = Array.prototype.slice;
      var cartesianProduct = function() {
          if (!arguments.length) throw new RangeError;
          var args = arraySlice.call(arguments),
              size = args.reduce(function(p, a) {
                  return p * a.length;
              }, 1),
              sizeOf = function() {
                  return size;
              },
              dim = args.length,
              that = Object.create(args, {
                  length: {
                      get: sizeOf
                  }
              });
          if (!size) throw new RangeError;
          hideProperty(that, 'index');
          addProperties(that, {
              valueOf: sizeOf,
              dim: dim,
              init: function() {
                  this.index = 0;
              },
              get: function() {
                  if (arguments.length !== this.length) return;
                  var result = [],
                      d = 0;
                  for (; d < dim; d++) {
                      var i = arguments[d];
                      if (i >= this[d].length) return;
                      result.push(this[d][i]);
                  }
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              },
              nth: function(n) {
                  var result = [],
                      d = 0;
                  for (; d < dim; d++) {
                      var l = this[d].length;
                      var i = n % l;
                      result.push(this[d][i]);
                      n -= i;
                      n /= l;
                  }
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              },
              next: function() {
                  if (this.index >= size) return;
                  var result = this.nth(this.index);
                  this.index++;
                  return result;
              }
          });
          addProperties(that, common);
          that.init();
          return that;
      };
      /* baseN */
      var baseN = function(ary, nelem, fun) {
                  if (!nelem) nelem = ary.length;
          if (nelem < 1) throw new RangeError;
          var base = ary.length,
                  size = Math.pow(base, nelem);
          var sizeOf = function() {
                  return size;
              },
              that = Object.create(ary.slice(), {
                  length: {
                      get: sizeOf
                  }
              });
          hideProperty(that, 'index');
          addProperties(that, {
              valueOf: sizeOf,
              init: function() {
                  that.index = 0;
              },
              nth: function(n) {
                  if (n >= size) return;
                  var result = [];
                  for (var i = 0; i < nelem; i++) {
                      var d = n % base;
                      result.push(ary[d])
                      n -= d; n /= base
                  }
                  return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
              },
              next: function() {
                  return this.nth(this.index++);
              }
          });
          addProperties(that, common);
          that.init();
          return (typeof (fun) === 'function') ? that.map(fun) : that;
      };
  
      /* export */
      var Combinatorics = Object.create(null);
      addProperties(Combinatorics, {
          C: C,
          P: P,
          factorial: factorial,
          factoradic: factoradic,
          cartesianProduct: cartesianProduct,
          combination: combination,
          bigCombination: bigCombination,
          permutation: permutation,
          permutationCombination: permutationCombination,
          power: power,
          baseN: baseN,
          VERSION: version
      });
      return Combinatorics;
  }));
  