How to optimize the generation of combinations?

4

I have the following code:

const montar = (volante, todos, posicao, restantes) => {
  if (restantes === 0) {
    return [volante];
  }

  const tamanho = todos.length - (restantes - 1);
  let novos = [];

  for (let indice = posicao; indice < tamanho; indice++) {
    const possivel = todos[indice];
    const volantes = montar([...volante, possivel], todos, indice + 1, restantes - 1);
    novos = [...novos, ...volantes];
  }

  return novos;
};

console.time('Calculando');
console.log(montar([], [1, 2, 3, 4, 5], 0, 3).length);
console.timeEnd('Calculando');

It generates all possible lottery flyers given the numbers that can be chosen and the amount per flyer. However, I believe that I decide recursion, the amount of memory allocated to calculate the possibilities of games with many possible numbers makes execution impracticable.

I would like to optimize the memory usage of this code to be able to generate, for example, all the mega-sena flyers (which are 6 numbers chosen from 1 to 60, generating 50.063.860 arrays ) without compromising performance .

    
asked by anonymous 20.11.2018 / 12:50

0 answers