simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

setPowerset.js (2084B)

      1 import { flatten } from '../../utils/array.js';
      2 import { factory } from '../../utils/factory.js';
      3 var name = 'setPowerset';
      4 var dependencies = ['typed', 'size', 'subset', 'compareNatural', 'Index'];
      5 export var createSetPowerset = /* #__PURE__ */factory(name, dependencies, _ref => {
      6   var {
      7     typed,
      8     size,
      9     subset,
     10     compareNatural,
     11     Index
     12   } = _ref;
     13 
     14   /**
     15    * Create the powerset of a (multi)set. (The powerset contains very possible subsets of a (multi)set.)
     16    * A multi-dimension array will be converted to a single-dimension array before the operation.
     17    *
     18    * Syntax:
     19    *
     20    *    math.setPowerset(set)
     21    *
     22    * Examples:
     23    *
     24    *    math.setPowerset([1, 2, 3])        // returns [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
     25    *
     26    * See also:
     27    *
     28    *    setCartesian
     29    *
     30    * @param {Array | Matrix}    a  A (multi)set
     31    * @return {Array}    The powerset of the (multi)set
     32    */
     33   return typed(name, {
     34     'Array | Matrix': function ArrayMatrix(a) {
     35       if (subset(size(a), new Index(0)) === 0) {
     36         // if empty, return empty
     37         return [];
     38       }
     39 
     40       var b = flatten(Array.isArray(a) ? a : a.toArray()).sort(compareNatural);
     41       var result = [];
     42       var number = 0;
     43 
     44       while (number.toString(2).length <= b.length) {
     45         result.push(_subset(b, number.toString(2).split('').reverse()));
     46         number++;
     47       } // can not return a matrix, because of the different size of the subarrays
     48 
     49 
     50       return _sort(result);
     51     }
     52   }); // create subset
     53 
     54   function _subset(array, bitarray) {
     55     var result = [];
     56 
     57     for (var i = 0; i < bitarray.length; i++) {
     58       if (bitarray[i] === '1') {
     59         result.push(array[i]);
     60       }
     61     }
     62 
     63     return result;
     64   } // sort subsests by length
     65 
     66 
     67   function _sort(array) {
     68     var temp = [];
     69 
     70     for (var i = array.length - 1; i > 0; i--) {
     71       for (var j = 0; j < i; j++) {
     72         if (array[j].length > array[j + 1].length) {
     73           temp = array[j];
     74           array[j] = array[j + 1];
     75           array[j + 1] = temp;
     76         }
     77       }
     78     }
     79 
     80     return array;
     81   }
     82 });