How to generate an array of every permutation of a sequence, with duplicates?

Question

I've had a look around this site but I have been unable to find an answer that includes duplicate elements. For example, given the array:

[1,2,3,4]

With a length of 3, A function should generate a list of every single possible combination with those numbers, using each one more than once:

[
  [1,1,1],
  [1,1,2],
  [1,1,3],
  ...
  [4,4,2],
  [4,4,3],
  [4,4,4]
]

I just haven't been able to get my head around the algorithm that I should use. I don't expect a code answer, but a push in the right direction would be appreciated.

I've tried using reduce like so:

const arr = [1, 2, 3, 4]
const len = 3

arr.reduce((acc, n) => {
    for (let i = 0; i < len; i++) {
        acc.push(/* ???? */)
    }
    return acc
}, [])

but I really don't know how to continue.

As a side note, ideally, I would like to do this as efficiently as possible.

Answer 1

One approach would be to use the length of the array as a base. You could then just access the array's elements from 0, and count up to the amount of combinations (array length ** length). If you're working with a small dataset, performance really shouldn't be an issue, but this answer is very performance oriented:

const getCombos = (arr, len) => {
  const base = arr.length
  const counter = Array(len).fill(base === 1 ? arr[0] : 0)
  if (base === 1) return [counter]
  const combos = []
  const increment = i => {
    if (counter[i] === base - 1) {
      counter[i] = 0
      increment(i - 1)
    } else {
      counter[i]++
    }
  }

  for (let i = base ** len; i--;) {
    const combo = []
    for (let j = 0; j < counter.length; j++) {
      combo.push(arr[counter[j]])
    }
    combos.push(combo)
    increment(counter.length - 1)
  }

  return combos
}

const combos = getCombos([1, 2, 3, 4], 3)
console.log(combos)

Answer 2

You could take an algorithm for getting a cartesian prduct with an array of three arrays with the wanted values.

var values = [1, 2, 3, 4],
    length = 3,
    result = Array
        .from({ length }, _ => values)
        .reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));

console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }