Convert nested loops to recursive function to compute combinations

Question

I did a job for compute all combinations of an array. The problem with my approach is that it only "generates" three-digit combinations (array length past 3), since I have 3 nested loops. If I wanted, however, that it generates values with 4 digits, I would have to nest one more loop.

Is there any way to create this same function, but recursively so that I can pass an argument by specifying the number of characters?

The expected result is an array of length L ^ N, being L the length of the array passed and N the number of characters per combination.

const data = ['a', 'b', 'c'];

function all(data) {
  const final = [];
  
  for (const c1 of data) {
    for (const c2 of data) {
      for (const c3 of data) {
        final.push(c1 + c2 + c3);
      }
    }
  }
  
  return final;
}

const x = all(data);
console.log(x.length, ':' , x);

Answer 1

You can use the recursion to pass the last parameter array generated until reaching the desired size:

const montar = (opcoes, calculado = []) => {
  // Verifica o critério de parada, que neste caso é já ter preenchido todas as posições do array
  if (opcoes.length === calculado.length) {
    return [calculado];
  }

  let novos = [];

  // Percorre as opções para preencher no final do array que foi dado
  for (const possivel of opcoes) {
    // Chama a mesma função novamente passando o opção do for como complemento ao array inicial
    const complementos = montar(opcoes, [...calculado, possivel]);
    // Concatena os novos compelementos a list previamente calculada
    novos = [...novos, ...complementos];
  }

  return novos;
};

console.time('Calculando');
console.log(montar(['a', 'b', 'c', 'd']));
console.timeEnd('Calculando');

Answer 2

You can create arrays using math to generate combinations. An example would be like this, using the fact that the possible combinations are raised array length to the same number:

const all = (arr) => {
  const length = arr.length;
  const total = Math.pow(length, length);
  const entry = Array.from(new Array(length));

  return Array.from(new Array(total)).map((_, i) => {
    return entry.map((_, j) => {
      const index = Math.floor(i / Math.pow(3, j)) % length;
      return arr[index];
    });
  });

}

const data = ['a', 'b', 'c'];
const x = all(data);
console.log(x.length, ':', JSON.stringify(x));

Another variant, more suited to the kind of logic you ask in the question would be:

const all = (original) => {
  const loop = (depth, acum = [], ...prev) => {
    if (depth === 0) {
      acum.push([...prev]);
      return acum;
    }

    for (let i = 0; i < original.length; i++) {
      loop(depth - 1, acum, ...prev, original[i]);
    }
    return acum;
  }
  return loop(original.length);
}

const data = ['a', 'b', 'c'];
const x = all(data);
console.log(x.length, ':', JSON.stringify(x));

Answer 3

This is possibly the ugliest and most inefficient code I’ve ever done. Don’t vote for it as correct.

But anyway, here’s a suggestion.

function all(data, len) {
  if (!len) return [];
  if (len === 1) return data;
  return recursao(data, len, data).sort();
}

function recursao(data, len, carry) {
  const arr = data.map(_ => [...carry]);

  for (let i = 0; i < data.length; ++i)
    for (let j = 0; j < arr[i].length; ++j)
      arr[i][j] += data[i];
   
  const final = arr.flat();
  return len > 2 ? recursao(data, len - 1, final) : final;
}

console.log(all(['a', 'b', 'c', 'd'], 2));
console.log(all(['a', 'b', 'c'], 3));
console.log(all(['a', 'b'], 4));