@jsmlt/jsmlt/distribution/random/index.js

'use strict';

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.randint = randint;
exports.rand = rand;
exports.sampleFisherYates = sampleFisherYates;
exports.sample = sample;

var _arrays = require('../arrays');

var Arrays = _interopRequireWildcard(_arrays);

var _search = require('../util/search');

var Search = _interopRequireWildcard(_search);

function _interopRequireWildcard(obj) { if (obj && obj.__esModule) { return obj; } else { var newObj = {}; if (obj != null) { for (var key in obj) { if (Object.prototype.hasOwnProperty.call(obj, key)) newObj[key] = obj[key]; } } newObj.default = obj; return newObj; } }

function _toConsumableArray(arr) { if (Array.isArray(arr)) { for (var i = 0, arr2 = Array(arr.length); i < arr.length; i++) { arr2[i] = arr[i]; } return arr2; } else { return Array.from(arr); } } // Internal dependencies


/**
 * Generate a random integer between a lower bound (inclusive) and an upper bound (exclusive).
 *
 * @param {number} a - Lower bound (inclusive)
 * @param {number} b - Upper bound (exclusive)
 * @param {number|Array.<number>} [shape = null] - If null, a single element is returned. If
 *   integer, an array of {shape} elements is returned. If an Array, random numbers are returned in
 *   a shape specified by this array. n-th element corresponds to the number of elements in the
 *   n-th dimension.
 * @return {Array.<mixed>}  Array of the specified with zero in all entries
 * @return {number|Array.<mixed>} Random integer in range [a,b), or a possibly nested array of
 *   random integers in range [a, b)
 */
function randint(a, b) {
  var shape = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : null;

  if (Number.isInteger(shape)) {
    // List of random integers
    return [].concat(_toConsumableArray(Array(shape))).map(function (x) {
      return randint(a, b);
    });
  } else if (Array.isArray(shape) && shape.length > 0) {
    if (shape.length === 1) {
      // Single shape item remaining; return list of integers
      return randint(a, b, shape[0]);
    }

    // Nested list of random integers
    return [].concat(_toConsumableArray(Array(shape[0]))).map(function () {
      return randint(a, b, shape.slice(1));
    });
  }

  // Single random integer
  return a + Math.floor((b - a) * Math.random());
}

/**
 * Generate a random number between a lower bound (inclusive) and an upper bound (exclusive).
 *
 * @param {number} a - Lower bound (inclusive)
 * @param {number} b - Upper bound (exclusive)
 * @return {number} Random number in range [a,b)
 */
function rand(a, b) {
  return a + Math.random() * (b - a);
}

/**
 * Take a random sample without replacement from an array. Uses the Fisher-Yates shuffling,
 * algorithm, modified to accomodate sampling.
 *
 * @param {Array.<mixed>} input Input array
 * @param {number} number Number of elements to sample from the input array
 * @return {Array.<mixed>} Array of length {number} with values sampled from the input array
 */
function sampleFisherYates(input, number) {
  // Copy input array
  var shuffledArray = input.slice(0);

  // Number of elements in the input array
  var numElements = input.length;

  for (var i = numElements - 1; i >= numElements - number; i -= 1) {
    var index = randint(0, i + 1);
    var tmp = shuffledArray[index];
    shuffledArray[index] = shuffledArray[i];
    shuffledArray[i] = tmp;
  }

  // Return the sampled values
  return shuffledArray.slice(numElements - number);
}

/**
 * Take a random sample with or without replacement from an array with uniform weights.
 *
 * @param {Array.<mixed>} input - Input array
 * @param {number} number - Number of elements to sample from the input array
 * @param {boolean} [withReplacement=true] - Whether to sample with (set to true) or without
 *   replacement (false)
 * @return {Array.<mixed>} Array of length {number} with values sampled from the input array
 */
function sampleUniform(input, number) {
  var withReplacement = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : true;

  // If sampling without replacement, use Fisher-Yates sampling
  if (!withReplacement) {
    return sampleFisherYates(input, number);
  }

  // If sampling with replacement, choose a random element each time
  var indices = randint(0, input.length, number);
  return indices.map(function (x) {
    return input[x];
  });
}

/**
 * Take a random sample with or without replacement from an array. Supports using sampling weights,
 * governing the probability of an item in the input array being selected.
 *
 * @param {Array.<mixed>} input - Input array
 * @param {number} number - Number of elements to sample from the input array
 * @param {boolean} [withReplacement=true] - Whether to sample with (set to true) or without
 *   replacement (false)
 * @param {Array.<number>|string} [weights='uniform'] - Weights to use for sampling. Defaults to
 *  'uniform',  which means all samples have equal probability of being selected. Alternatively, you
 *  can pass an array of weights, containing a single weight for each element in the input array
 * @return {Array.<mixed>} Array of length {number} with values sampled from the input array
 */
function sample(input, number) {
  var withReplacement = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : true;
  var weights = arguments.length > 3 && arguments[3] !== undefined ? arguments[3] : 'uniform';

  if (Array.isArray(weights)) {
    if (weights.length !== input.length) {
      throw new Error('Weights array length does not equal input array length.');
    }

    if (!withReplacement && number > weights.filter(function (x) {
      return x > 0;
    }).length) {
      throw new Error('Invalid sampling quantity specified: sampling without replacement cannot sample more elements than the number of non-zero weights in the weights array.');
    }
  } else if (weights !== 'uniform') {
    throw new Error('Invalid value specified for "weights".');
  }

  if (!withReplacement && number > input.length) {
    throw new Error('Invalid sampling quantity specified: sampling without replacement cannot sample more elements than the number of input elements.');
  }

  // Use the uniform sampling method if the user has specified uniform weights
  if (weights === 'uniform') {
    return sampleUniform(input, number, withReplacement);
  }

  // Copy weights vector
  var useWeights = weights.slice();

  var calculateCumWeights = function calculateCumWeights(localWeights) {
    return localWeights.reduce(function (r, a, i) {
      return [].concat(_toConsumableArray(r), [i > 0 ? r[i - 1] + a : a]);
    }, []);
  };

  var sampleSingle = function sampleSingle(useCumWeights) {
    // Generate a random number, and find the interval in the array of cumulative weights to which
    // it corresponds. We use this index as the sampled array index, which corresponds to weighted
    // sampling
    var randomNumber = rand(0, useCumWeights[useCumWeights.length - 1]);
    return Search.binaryIntervalSearch([0].concat(_toConsumableArray(useCumWeights)), randomNumber);
  };

  if (withReplacement) {
    // Sample with replacement, i.e., randomly sample one element n times in a row
    var cumWeights = calculateCumWeights(useWeights);

    return Arrays.zeros(number).map(function () {
      return input[sampleSingle(cumWeights)];
    });
  }

  // Sample without replacement: randomly sample one element, remove it from the list of elements
  // that can still be sampled and the weights list, and sample from the remaining elements

  // Copy input
  var useInput = input.slice();

  // List of elements sampled
  var samples = [];

  while (samples.length < number) {
    // Sample from remaining inputs
    var _cumWeights = calculateCumWeights(useWeights);
    var useSample = sampleSingle(_cumWeights);
    samples.push(useInput[useSample]);

    // Remove sampled element from input elements and weights lists
    useInput.splice(useSample, 1);
    useWeights.splice(useSample, 1);
  }

  return samples;
}