C++ How to generate the set of cartesian product of n-dimensional tuples

Question

I wish to generate some data that represents the co-ordinates of a cloud of points representing an n-cube of n dimensions. These points should be evenly distributed throughout the n-space and should be able to be generated with a user-defined spacing between them. This data will be stored in an array.

Answer 1

I have found an implementation of a cartesian product using Boost.MPL.

There is an actual Cartesian product in Boost as well but that is a preprocessor directive, I assume it is of no use for you.

Answer 2

To keep things simple here's an example for an ordinary cube, ie one with 3 dimensions. Let it have side length 1 and suppose you want points spaced at intervals of 1/n. (This is leading to a uniform rectangular distribution of points, not entirely sure that this is what you want).

Now some pseudo-code:

for i=0;i<=n;i++   //NB i<=n because there will be n+1 points along each axis-parallel line
    for j=0;j<=n;j++
        for k=0;k<=n;k++
            addPointAt(i/n,j/n,k/n)  //float arithmetic required here

Note that this is not the Cartesian product of anything but seems to satisfy (a special case of) your criteria. If you want the points spaced differently, adjust the loop start and end indices or the interval size.

To generalise this to any specified higher dimension is easy, add more loops.

To generalise to any higher dimension which is not known until run time is only slightly more difficult. Instead of declaring an N-dimensional array, declare a 1-D array with the same number of elements. Then you have to write the index arithmetic explicitly instead of having the compiler write it for you.

I expect that you are now going to tell me that this is not what you want ! If it isn't could you clarify.

Answer 3

You can do this recursively(pseudocode):

Function Hypercube(int dimensions, int current, string partialCoords)
{
  for i=0, i<=steps, i++
  {
    if(current==dimensions)
      print partialCoords + ", " + i + ")/n";
    else if current==0
      Hypercube(dimensions, current+1, "( "+i);
    else
      Hypercube(dimensions, current+1, partialCoords+", "+i);
  }

}

You call it: Hypercube(n,0,""); This will print the coordinates of all points, but you can also store them in a structure.