Algorithm to generate all sets of m points in n x n x n cubic lattice which are unique under symmetry

Question

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)

Answer 1

Basic concept:

(1) We can view point (0,0,0) simply as 000. Each point in the lattice now falls in a simple sequence. The first point is 000, then 001, then 010 011 100 101 110 and 111. This is the order that you will try adding them to the point-set.

(2) Similarly, the set {(0,0,0),(0,0,1),(0,1,0)} can simply be seen as 000001010, and the set {(0,0,0),(0,1,0),(0,0,1)} can simply be seen as 000010001. Two different sets can't have the same sequence, and you can easily view 000001010 as being numerically or alphabetically less than 000010001. Let's call this the set-value. Every possible set of N points now has a set-value, and all possible sets of N points now fall in a simple well-ordered list.

(3) Every isomorphic group of point-sets has exactly one member that will have the lowest set-value. Those are the only ones where we actually do "useful computation".

(4) Here's the part that will need significant work. Before you run solve(set_of_points+new_point), you want to see if any isomorphism would lower the set-value for set_of_points+new_point. If any isomorphism would lower the set value then this is NOT a lowest value member of the isomorphic-set. We skip doing any work on this new_point. We are also skipping all of the recursive work we would have done inside of this solve(set_of_points,candidate_point).

solve(set_of_points,new_point) {
 set_of_points = set_of_points + new_point
 do some useful computation here
 if set_of_points.size = m, compute how many isomophisms exist, apply that multiple, finish
 for(candidate_point = new_point+1 to last_point) { /skips point-permutations for free!/
  if ISOMORPH_TESTS_CANNOT_LOWER_VALUE_OF(set_of_points+candidate_point) {
   solve(set_of_points,candidate_point);
  }
 }
}

Answer 2

taking the notation of the answer above.

lets first define the symmertry proposed by the function rotate(direction, number_of_time)

solution:

(1) create hash of all set of the permutation with flag=0 on each. for example for n=2,m=2 000,001=0 000,010=0 000,011=0 ect'...

(2) start from init set, for example i=000,001

(3) rotate the set i to all direction using the rotate function (or any other symmetry you like) for example, the rotate function should be call 24 times for each permutation of the rotation.

explenation: any number 1-6 can be in front of you and each of the number can be rotate 4 times, therefore 6*4=24

(4) for each set returened from the combination, set the flag of hash to 1 (it has already symmetrical set)

(5) update i to the next set for example i=000,010

(6) if the set i in the hash already marked, go to (5) otherwise go to (3)

we are done when all the hash is marked as 1.

Answer 3

Note: I think only about mirror symmetries, not rotational symmetries here.

Let's suppose we have a (hyper) cube of d dimensions, each n unit long (a Rubik's cube would be d=3, n=3).

A naive algorithm would generate n^d combinations of points, and check each for a symmetry clash with all others.

If we represent a combination of points as a bit vector n^d bits long, we can use a map (bit vector -> boolean) to mark all the symmetries of the bit vector with true. We could then skip a combination if it's already marked in the map.

This approach is very space-inefficient: it takes a map with 2^(n^d) entries, that is, a bitmap with this many bits. (For Rubik's cube, it would be 2^27 = 128Mbit = 16 Mbytes.)

We can only remember the canonical representations, that is, such bit vectors that have the smallest integer value, if represented as a n^d-bit unsigned word. When we generate a new permutation of points, we generate all its symmetries, and only check if we've seen the symmetry with the smallest numerical value. This will allow us to store a map wit only 2^n bits (just 1 byte for the Rubik's cube), because we have 2^d symmetries. It makes us generate these 2^d symmetries on each step, though, so we spend O(2^(d^n + d)) = O(2^(d^n) * 2^d) time. Still poor.

We can apply the idea from the previous paragraph to the 1-dimensional case. To generate all combinations in a vector of length d, we can just increment a binary number d bits long, starting from all 0s. Let's divide our vector to two d/2-long segments, e.g. left and right. We can notice that for each 1 bit in the left segment we only need to see combinations that have 1 bit in the symmetric position of the right section. Otherwise we would have already generated a symmetric combination earlier, when the positions of the bits were swapped, and the 0 came before the 1. This way, for every bit position in the right half (r), and the symmetric position in the left half (l) we only need to generate 3 combinations: (l = 0, r = 0); (l = 1, r = 1); (l = 1, r = 0). Thus we only need to generate 2^(d/2) permutations of a vector of length d, yielding 3 combinations for each permutation.

A cube of d dimensions can be constructed of n^(d-1) vectors. The trick above gives us the vectors cheaper than the naive approach. To generate a cube, we need O(n^(d-1) * 2^(d/2)) time.

If we look at the cube along the dimension of our 1-dimensional vectors, we can see that we don't have to check for symmetry along this dimension: while generating the cubes, we eliminate symmetries for each involved vector.

Now if we look across this dimension, we can reuse the same trick.

When we look across, we look at e.g. first bits of vectors making a particular plane. These bits represent a 1-dimensional bit vector. We can eliminate most combinations of its bits from symmetry reasons, as described above. So if we pick a particular 1-d vector of a cube (e.g. leftmost topmost), we can eliminate many vectors of the same plane (e.g. top) based on the value of a particular bit. So for a vector in a mirror-symmetrical position on the plane, we can avoid generating all combinations might have that bit set (or unset), reducing the number of vectors we have to generate for a particular plane drastically. Each eliminated bit halves the number of possible vectors at the mirror-reflected position. This gives us a sequence of planes without symmetrical counterparts along each dimension.

This trick can be applied to further limit generation of permutations of the following planes along a third dimension, etc.

Though not a complete algorithm, I hope this helps.