The number of combinations that need to be checked get exponentially larger as the dimension n of the hypercube increases. The problem with this algorithm is that it's extremely inefficient. This would continue until all combinations had been checked. If it did, and the hamming distance was exactly m, it would be added to the m-face list. If the hamming distance was > m, the combination would be ignored, otherwise we would continue building the combination until it contained 2^m vertices. Each time a vertex was added to the combination, the hamming distance would be checked between all vertices in the combination. My algorithm produced lists of m-faces by recursively building combinations of vertices. ,, , and form a face (2-face) because they differ by 2 bits (i.e.

If a combination of 2^m vertices differ by exactly m bits, then they form an m-face.įor example, and form an edge (1-face) because they differ by 1 bit. One solution (which I currently have working) is to use the hamming distance between vertices' binary representations to determine whether or not they are part of an m-face. an n-face is represented by a length 2^n array of vertices. Same goes for cels and any other n-face, i.e. Note that a face is not an array of edge arrays, instead an array of the vertices that represent the face. , ]), we would have: > getMFaces(1, 3, vertices)Įdges in a 2-dimensional hypercube (a face) would give: > getMFaces(1, 2, vertices)įaces (2-faces) in a cube would give: > getMFaces(2, 3, vertices) If we assume vertices is an ordered array of binary representations of vertices in a cube (i.e.

Say we wanted to get an array of edges (1-faces) in a cube (3-dimensional hypercube). That may have been a confusing way to word it, so here are a few examples: I'm attempting to design an algorithm that, given n, m, and vertices (where n = the dimension of a hypercube, m = the dimension of the faces we're trying to generate, and vertices is an ordered list of vertices in an n-dimensional hypercube), returns an array of arrays of vertices representing m-faces in an n-dimensional hypercube.

Hypercube edges