Re: Fastest way to generate all combinations?



Bryan said:

I want to generate a list of all possible combinations of x, y, z where
each of xyz can range from 0 -> 1000. What is the fastest way to do
this in C++?

Im using 3 nested for loops right now, but I was wondering if there was
a more efficient algorithm for this?

1000 * 1000 * 1000 * sizeof(int) is, best case, getting on for 2 Gigabytes,
and may well be double that. I have to ask - are you *sure* you want to do
this?

Anyway, one obvious optimisation is:

for(unsigned long n = 0; n < 1000000000UL; n++)
{
mylist[n].x = n / 1000000UL;
mylist[n].y = (n / 1000UL) % 1000UL;
mylist[n].z = n % 1000UL;
}

which eliminates your inner loops.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
.



Relevant Pages

  • Re: Fastest way to generate all combinations?
    ... Bryan wrote: ... each of xyz can range from 0 -> 1000. ... Im using 3 nested for loops right now, but I was wondering if there was ... That way you can avoid storing huge arrays of combinations. ...
    (comp.programming)
  • Re: Fastest way to generate all combinations?
    ... Bryan wrote: ... each of xyz can range from 0 -> 1000. ... Im using 3 nested for loops right now, but I was wondering if there was ... a more efficient algorithm for this? ...
    (comp.programming)
  • Re: Fastest way to generate all combinations?
    ... Bryan wrote: ... each of xyz can range from 0 -> 1000. ... Im using 3 nested for loops right now, but I was wondering if there was a more efficient algorithm for this? ...
    (comp.programming)
  • Re: Fastest way to generate all combinations?
    ... each of xyz can range from 0 -> 1000. ... Im using 3 nested for loops right now, but I was wondering if there was ... Anyway, one obvious optimisation is: ... calculations would be about the same -- calculating an array index ...
    (comp.programming)
  • Re: /bin/bash
    ... >> control variables that I come across in loops, espcially 'for' loops, ... Doesn't explain the equally common use of xyz and abc, ...
    (comp.os.linux.misc)