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

Right away I noticed a few patterns

• There are n different sized gaps between vertex indexes
• The ith gap is 2^i

Then I noticed that the edge list of dimension n builds off of the edge list of dimension n-1 recursively. This makes sense since n-hypercube geometries build off of n-1-hypercube geometries.

Using Recursion

I rearranged my spreadsheet and made sheets for n = 1..4 and m = 1..3:

m = 1 for dimensions 1 - 4

Here, v represents the ordered array of vertices, a represents the output m-face array, each column represents an m-face, and the colored outlines show the relationships to the m-face list in lower dimensions (the recursive relationship to lower dimensions).

The numbers in the black squares represent the index of the vertex in v.

I was able to deduce the following recursive algorithm using the patterns I noticed (where m = 1 is the dimension of the face and n is the dimension of the hypercube). Instead of producing an array of vertices, it produces an array of indexes i that represent the ith vertex:

generateEdges(n) {    // m is always 1 here since we're only producing edges
  if (n === 1) {
    return [[0, 1]];
  } else {
    // we start with the edges from the previous dimension
    const prev = generateEdges(n-1);
    // we duplicate these edges and add 2^(n-1) to each index
    const curr = prev.map(edge => edge.map(i => i   2**(n-1)));
    
    const next = [];
    // we only care about the prev.length - 2**(n-2) indexes
    // since these are the new edges added in the previous dimension
    for (let i = prev.length - 2**(n-2); i < prev.length; i  ) {
      // we form new edges by combining index [i][0] and [i][1] of prev and curr
      next.push([prev[i][0], curr[i][0]]);
      next.push([prev[i][1], curr[i][1]]);
    }

    // finally, we combine all 3 to get our new edge list
    return [...prev, ...curr, ...next];
  }
}

This algorithm successfully produces edge lists for dimension n and is much more efficient than having to check every possible combination of vertices (as was the case when using the hamming distance).

The down side is that this algorithm produces indexes, so you'll have to go through and map the indexes to actual vertices afterwards. It produces edge lists almost instantly for dimensions up to 14 or 15.

I then made sheets for m = 2 and m = 3 (faces and cells) to see if I could draw any sort of connection and extend my recursive algorithm to work for all ms:

m = 2 for dimensions 1 - 4

m = 3 for dimensions 1 - 4

This is where I'm stuck

I can tell there's some sort of pattern that extends across all ms, I'm just overwhelmed with the task of pinpointing it and translating it into an algorithm.

I can tell that m-face lists for m > 1 are built in a similar way to the recursive algorithm I provided for m = 1, I'm just not able to figure out what needs to be added.

I apologize for the long, confusing post. As you can probably tell by my need for visualization, I'm not great with linear algebra, so there may be some obvious mathematical principal or something that I'm missing.

Any ideas or help with this algorithm would be greatly appreciated. I'm trying to make it as efficient as possible– maybe implementing it using loops would be more efficient than recursion, but I'm just trying to get a working algorithm before I try to improve efficiency.

As this is my first post, I'm not 100% sure if I'm posting this question in the right location, so please let me know if I'm in the wrong forum. I could see how this sort of question may be a better fit for a more algorithm or math-centric forum, so let me know if there's a better place to post this!

CodePudding user response：

Every m-sized subset of the n dimensions is an "orientation" with those m dimensions "free". For each orientation, you can generate a face by generating all 2^m combinations of the m coordinates in the m free dimensions, while holding the coordinates for the other dimensions fixed. Each of the 2^n-m combinations of coordinates for the other dimensions is the "position" of a different face.

The number of orientations is C(n,m) = n!/m!(n-m)!, so you should end up with C(n,m) * 2^n-m faces overall.

The number of edges in a cube, for example = C(3,1) * 2² = 3 * 4 = 12.

The number of faces on a cube is C(3,2) * 2 = 3 * 2 = 6.

It's not too difficult to generate all faces:

• For each orientation, determine the free and fixed dimensions
  • Count in binary using the fixed dimensions to find all the face positions
    • For each face, count in binary over the free dimensions to generate its vertices.