How to optimize the generation of combinations?

Asked

Viewed 172 times

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 wheels given the numbers that can be chosen and the amount per steering wheel. However, I believe I decide recursion, the amount of memory allocated to calculate the possibilities of games with many possible numbers makes execution unfeasible.

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

  • What you can do is a page and return N numbers per page

  • 1

    Have you tried to calculate how many bytes these combinations will occupy? You have 50 million vectors of 6 numbers; no overhead of arrays, you need to allocate at least enough to 300 million integers (6 * 50 million); hypothetically, if we can say that we only need 1 byte for these integers, then it’s 300 million bytes, 286 Mib. Now, considering a traditional size of 4 bytes, it’s 1.2 billion bytes. just over 1 Gib. That’s without considering the overheads arrays...

  • 1

    @Jeffersonquesado makes sense, I had not stopped to calculate!

  • 1

    I can suggest a combination compression. A number that, through a decompression process, becomes the appropriate combination. Thus, you would only need to send the decompression function and something to indicate "everything from 0 to 50.063.860"... matters?

  • 1

    @Jeffersonquesado believe that yes... the intention is to generate all the combinations in the same end

No answers

Browser other questions tagged

You are not signed in. Login or sign up in order to post.