Find all combinations from given ordered choices.

README.md

Combinations

Find all combinations from given ordered choices.

Implementation

function getAllCombinations<T>(slotsChoices: T[][]) {
  const searchSpaceSizes = slotsChoices.map(choices => choices.length)
  const solutionSize = searchSpaceSizes.reduce((a, b) => a * b)
  const slots = new Array(solutionSize).fill(slotsChoices)
  const solutions = slots.map((slotsChoices, i) => {
    const indexesToPick = decodeIndex(i, searchSpaceSizes)
    return indexesToPick.map((index, j) => {
      const choices = slotsChoices[j]
      return choices[index]
    })
  })
  return solutions
}

function decodeIndex(index: number, searchSpaceSizes: number[]) {
  const indexesToPick = []
  let divident = index
  for (let i = 0; i < searchSpaceSizes.length; i++) {
    const [quotient, remainder] = euclideanDivision(divident, searchSpaceSizes[i])
    indexesToPick[i] = remainder
    divident = quotient
  }
  return indexesToPick
}

function euclideanDivision(divident: number, divisor: number) {
  const remainder = divident % divisor;
  const quotient =  (divident - remainder) / divisor;
  return [quotient, remainder]
}

Usage

const slotsChoices = [
  [0, 1, 2, 3],
  [0, 1],
  [0, 1, 2]
]

const solutions = getAllCombinations(slotsChoices)
/**
solutions = [
  [0, 0, 0], [1, 0, 0], [2, 0, 0], [3, 0, 0], 
  [0, 1, 0], [1, 1, 0], [2, 1, 0], [3, 1, 0], 
  [0, 0, 1], [1, 0, 1], [2, 0, 1], [3, 0, 1], 
  [0, 1, 1], [1, 1, 1], [2, 1, 1], [3, 1, 1], 
  [0, 0, 2], [1, 0, 2], [2, 0, 2], [3, 0, 2], 
  [0, 1, 2], [1, 1, 2], [2, 1, 2], [3, 1, 2]
]
*/

Refs

https://stackoverflow.com/a/64138214/3617380

combinations.js

function getAllCombinations(slotsChoices) {
    const searchSpaceSizes = slotsChoices.map(choices => choices.length);
    const solutionSize = searchSpaceSizes.reduce((a, b) => a * b);
    const slots = new Array(solutionSize).fill(slotsChoices);
    const solutions = slots.map((slotsChoices, i) => {
        const indexesToPick = decodeIndex(i, searchSpaceSizes);
        return indexesToPick.map((index, j) => {
            const choices = slotsChoices[j];
            return choices[index];
        });
    });
    return solutions;
}

function decodeIndex(index, searchSpaceSizes) {
    const indexesToPick = [];
    let divident = index;
    for (let i = 0; i < searchSpaceSizes.length; i++) {
        const [quotient, remainder] = euclideanDivision(divident, searchSpaceSizes[i]);
        indexesToPick[i] = remainder;
        divident = quotient;
    }
    return indexesToPick;
}

function euclideanDivision(divident, divisor) {
    const remainder = divident % divisor;
    const quotient = (divident - remainder) / divisor;
    return [quotient, remainder];
}

combinations.ts

function getAllCombinations<T>(slotsChoices: T[][]) {
  const searchSpaceSizes = slotsChoices.map(choices => choices.length)
  const solutionSize = searchSpaceSizes.reduce((a, b) => a * b)
  const slots = new Array(solutionSize).fill(slotsChoices)
  const solutions = slots.map((slotsChoices, i) => {
    const indexesToPick = decodeIndex(i, searchSpaceSizes)
    return indexesToPick.map((index, j) => {
      const choices = slotsChoices[j]
      return choices[index]
    })
  })
  return solutions
}

function decodeIndex(index: number, searchSpaceSizes: number[]) {
  const indexesToPick = []
  let divident = index
  for (let i = 0; i < searchSpaceSizes.length; i++) {
    const [quotient, remainder] = euclideanDivision(divident, searchSpaceSizes[i])
    indexesToPick[i] = remainder
    divident = quotient
  }
  return indexesToPick
}

function euclideanDivision(divident: number, divisor: number) {
  const remainder = divident % divisor;
  const quotient =  (divident - remainder) / divisor;
  return [quotient, remainder]
}