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?

Thanks

Bryan said:

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)

Bryan wrote:
Its best not to generate the combinations then use them, but rather to
call the routine that consumes the combinations inside those generating
them. That way you can avoid storing huge arrays of combinations.

Bryan writes:
As it happens, I posted a general variant of that a week ago.
After asking a similar question and getting a few nudges in
the right direction.
Message <hbf.20060724d1be@bombur.uio.no>,
thread 'Series of all N-tuples of natural numbers'.
With just N=3 I you can skip some of the complexity, and
possible gain speed by doing some of the recursion "by hand".

--
Hallvard

Bryan wrote:
Do you really want combinations or tuples? Combinations are sets, so
if you generate <1,2,3> you would skip <2,1,3>. You'd also never
generate <1,1,2> .

Bryan wrote:

In article <xcGdnbPbkdS3EVLZnZ2dnUVZ8qWdnZ2d@bt.com>,
Richard Heathfield <invalid@invalid.invalid> wrote:
I guess one would have to measure both to be sure, but -- what
is it that makes this an optimization? it seems to me that the
calculations would be about the same -- calculating an array index
for nested loops versus calculating x,y,z for your version, and
if the loops are nested correctly memory will be accessed in the
same order, so there shouldn't be issues with caching. What am I
not getting?

--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.

In article <zxLzg.236$1f6.137@newssvr27.news.prodigy.net>,
Bryan <spam@nospam.com> wrote:
Wrong question. The correct question is "What is the simplest way to
do this in C++?". The next question is "Is doing it this way fast
enough?". Is there some reason why the obvious implementation isn't
doing it for you?

Alan
--
Defendit numerus

Richard Heathfield wrote:

I admit I haven't timed it, but I find it hard to believe that adding
two divides and two modulus operations to the inner loop will speed it
up, even if it does remove a test-and-branch.

Of course, some compilers for some languages might bit-twiddle the
expensive operations away...

-- chris

Richard Heathfield writes:
for(unsigned long n = 0; n < 1000UL * 1024 * 1024; n++)
{
mylist[n].x = n >> 20;
mylist[n].y = (n >> 10) & 1023;
mylist[n].z = n & 1023;
}

--
Hallvard

I wrote:
Duh... Sorry.

--
Hallvard

blmblm@myrealbox.com said:

Er, never mind. I think I was not - um - thinking. :-)

What you're not getting is that I saved 1,001,000 jump statements, and it
only cost me 2,000,000,000 mods and 2,000,000 divisions!

(eek!)

--
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)