JS: Ordered Selections With Replacement

orderedSelectionsWithReplacement.js

function orderedSelectionsWithReplacement(numChoices, subsetSize)
{
  var subsets = [], i, advance, picks = new Array(subsetSize).fill(null), pos = 0;
  while (true)
  {
    //try to find something that has yet to be used
    advance = false;
    for (i = picks[pos]||0; i < numChoices; i++)
    {
      picks[pos] = i;
      advance = true;
      break;
    }
    if (advance && pos >= subsetSize - 1)
    {
      //we have incremented the final item and need to return it
      subsets.push(picks.slice()); //copy into output array
      picks[pos] += 1; //move endpoint to next candidate
    }
    else if (advance)
    {
      //ready to move to the next item. Starting at previous value
      //ensures that we only generate increasing-order choices in the subset,
      //which ensures that we remove duplicates (i.e. [1,3,4] is canonical; [3,1,4] is equivalent and omitted)
      pos += 1;
      picks[pos] = picks[pos - 1]
    }
    else if (pos > 0)
    {
      //time to backtrack to the previous spot, if we're not at the first spot
      picks[pos] = null;
      pos -= 1;
      picks[pos] += 1;
    }
    else if (picks[0] < numChoices - 1)
    {
      //next turn of while() loop will advance initial item to next position
    }
    else
    {
      //we've enumerated everything and are now done
      return subsets;
    }
  }
}

console.log(orderedSelectionsWithReplacement(4, 3));
/* result:
[
  [ 0, 0, 0 ],
  [ 0, 0, 1 ],
  [ 0, 0, 2 ],
  [ 0, 0, 3 ],
  [ 0, 1, 1 ],
  [ 0, 1, 2 ],
  [ 0, 1, 3 ],
  [ 0, 2, 2 ],
  [ 0, 2, 3 ],
  [ 0, 3, 3 ],
  [ 1, 1, 1 ],
  [ 1, 1, 2 ],
  [ 1, 1, 3 ],
  [ 1, 2, 2 ],
  [ 1, 2, 3 ],
  [ 1, 3, 3 ],
  [ 2, 2, 2 ],
  [ 2, 2, 3 ],
  [ 2, 3, 3 ],
  [ 3, 3, 3 ]
]
*/