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; }

Answer 3

Picture an ancient mechanical rotary counter:

To count from 00000 to 99999 you rotate the rightmost wheel until it reaches 9, then it resets to 0 and the second right wheel is advanced by 1 etc.

In code: locate the rightmost wheel which position is less than the max. digit. Advance that wheel by 1 and reset all wheels on the right of it to 0. Repeat until there's no such wheel.

function counter(digits, size) {
    let wheels = Array(size).fill(0),
        len = digits.length,
        res = [];

    while (1) {
        res.push(wheels.map(n => digits[n]));
        for (let i = size - 1; i >= 0; i--) {
            if (wheels[i] < len - 1) {
                wheels[i]++;
                wheels.fill(0, i + 1);
                break;
            }
            if (i === 0)
                return res;
        }
    }
}

all = counter('1234', 3)
console.log(...all.map(c => c.join('')))

Performance measures:

const kobe = (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
}

function nina(values, length) {
    return Array
        .from({length}, _ => values)
        .reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
}

function trincot(digits, size) {
    if (!size) return [[]]; // base case
    let shorter = trincot(digits, size - 1); // get all solutions for smaller size
    // ...and prefix each of those with each possible digit
    return Array.from(digits, dig => shorter.map(arr => [dig, ...arr])).flat();
}

function georg(digits, size) {
    let wheels = Array(size).fill(0),
        len = digits.length,
        res = [];

    while (1) {
        res.push(wheels.map(n => digits[n]));
        for (let i = size - 1; i >= 0; i--) {
            if (wheels[i] < len - 1) {
                wheels[i]++;
                wheels.fill(0, i + 1);
                break;
            }
            if (i === 0)
                return res;
        }
    }
}

const gilad = (A, k) =>
  k ? gilad(A, k - 1).reduce((a, s) => a.concat(A.map(e => s.concat(e))), []) : [[]]


//////////////////////////////////////////////////////////////

fns = [kobe, nina, trincot, georg, gilad];
ary = [0, 1, 2, 3, 4, 5, 6, 7, 8]
size = 5
res = []

for (f of fns) {
    console.time(f.name);
    res.push(f(ary, size));
    console.timeEnd(f.name)
}

Using the same technique to generate cartesian products:

function product(...arrays) {
    let size = arrays.length,
        wheels = Array(size).fill(0),
        lens = arrays.map(a => a.length),
        res = [];

    while (1) {
        res.push(wheels.map((n, w) => arrays[w][n]));
        for (let w = size - 1; w >= 0; w--) {
            if (wheels[w] < lens[w] - 1) {
                wheels[w]++;
                wheels.fill(0, w + 1);
                break;
            }
            if (w === 0)
                return res;
        }
    }
}

// demo

p = product('12', 'abcde', 'XYZ')
console.log(...p.map(q => q.join('')))

// some timings

// https://stackoverflow.com/a/43053803/989121
const f = (a, b) => [].concat(...a.map(d => b.map(e => [].concat(d, e))));
const cartesian = (a, b, ...c) => (b ? cartesian(f(a, b), ...c) : a);

arrays = Array(7).fill(0).map(_ => Array(5).fill(0)) // 5**7=78125 combinations

console.time('func')
cartesian(...arrays)
console.timeEnd('func')

console.time('iter')
product(...arrays)
console.timeEnd('iter')

Answer 4

Maybe also add the recursive solution:

function counter(digits, size) {
    if (!size) return [[]]; // base case
    let shorter = counter(digits, size-1); // get all solutions for smaller size
    // ...and prefix each of those with each possible digit
    return Array.from(digits, dig => shorter.map(arr => [dig, ...arr])).flat();
}
// demo
let all = counter("1234", 3);
console.log(...all.map(c => c.join("")));

Answer 5

This is known as "n multichoose k" and has the following recurrence relation:

function f(ns, n, k){
  if (n == 0)
    return []
  if (k == 0)
    return [[]]
    
  return f(ns, n - 1, k).concat(
    f(ns, n, k - 1).map(s => s.concat(ns[n-1])))
}

var multiset = [1, 2, 3, 4]
var k = 3
console.log(JSON.stringify(f(multiset, multiset.length, k)))

An alternative, as others have answered, is to also include every permutation of every combination. One way is to append each element to each combination as we build towards the final length. (This idea is similar to trincot's.)

const f = (A, k) =>
  k ? f(A, k - 1).reduce((a, s) => a.concat(A.map(e => s.concat(e))), []) : [[]]

var A = [1, 2, 3, 4]
var k = 3
console.log(JSON.stringify(f(A, k)))