I am implementing an algorithm which is going to be quite computationally complex, and want to try to make sure I'm not doing unnecessary work.
There is an n x n x n cubic lattice, e.g. if n=2 this consists of (0,0,0), (0,1,0), (1,0,0), (1,1,0), (0,1,1), (0,0,1), (1,0,1), (1,1,1).
From this lattice I will be recursively generating all sets of m points, something like:
solve(set_of_points) {
if set_of_points.size = m, finish
do some useful computation here
for each point in lattice not in set_of_points:
solve(set_of_points + new_point);
}
This can then be called starting with an empty set_of_points.
The nature of the problem is such that I don't actually need every permutation of m points, just the ones which are unique under natural symmetries of the cube.
For example, take a 2x2x2 cube and suppose we want all sets of 1 point. Under the basic algorithm above, there are 8 different sets of 1 point.
However, using the symmetries of the cube we can reduce this down to 1 unique set of 1 points, since all of the original 8 are equivalent under symmetries of the cube (they are all 'corners' in this case).
If the cube is 2x2x2 and m=2, there are 28 sets in the basic algorithm, but this reduces to just 3 under symmetry (e.g. { (0,0,0), (1,0,0) }, { (0,0,0), (1,1,0) }, { (0,0,0), (1,1,1) } )
Obviously doing the computation on 3 sets of points is much better than 28, so my question is how do I go about not generating sets of points which are symmetrically equivalent to a set already generated? Or if this isn't possible, how can I at least reduce the number of sets a little.
(Note - if m=1 this is relatively easy - just pick the points which are closer to (0,0,0) than any of the other vertices, with a little fudging at the boundaries. It's for m>1 that this gets to be a real problem)