sampling by relative frequency distribution

proportional-selection.js

/**
 * given a sorted list and a number to search returns the right insertion index to maintain sorted order
 * @param list {number[]}
 * @param x {number} 
 */
const bisectRight = (list, x) => {
  if(list.length === 0) {
    return 0
  }
  let first = 0
  let last = list.length - 1
  let mid = 0
  while (first<=last){
    mid = Math.floor((last + first) / 2)
    if(list[mid] === x) {
      return mid + 1
    }
    if(x < list[mid] ){
      last = mid - 1
    } else if(x > list[mid]){
      first = mid + 1
    }
  }
  if(x < list[mid]){
    return mid
  }
  return mid + 1
}

/**
 * return a cumulative sum array for given array
 * @param {*} arr {number[]} 
 * @param {*} precision {number}
 */
const cumsum = (arr, precision) => {
  let list = arr.slice()
  for(let i = 0; i < list.length; i++){
    if(i > 0) {
      list[i] = parseFloat((list[i] + list[i - 1]).toPrecision(precision || 10))
    }
  }
  return list
}

/**
 * sample from labels based on given relative frequency distribution array
 * @param {*} labels {any[]}
 * @param {*} pd {number[]}
 */
const samplepd = (labels, pd) => {
  if(labels.length !== pd.length) {
    throw(new Error("labels.length doesn't match pd.length"))
  }
  let isInValidPd = pd.reduce((a,b) => {return a+b}) !== 1
  if(isInValidPd) {
    throw(new Error("invalid distribution: distribution doesn't reduce to sum 1.0"))  
  }
  let cumpb = cumsum(pd, 10)
  let draw = Math.random()
  let idx = bisectRight(cumpb, draw)
  return labels[idx]
}

module.exports = {
  samplepd,
  bisectRight,
  cumsum
}