javascriptalgorithmrecursionn-dimensionalhypercube

Algorithm to dynamically generate m-face list for n-dimensional hypercube

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.

That may have been a confusing way to word it, so here are a few examples:

Say we wanted to get an array of edges (1-faces) in a cube (3-dimensional hypercube). If we assume vertices is an ordered array of binary representations of vertices in a cube (i.e. [[0, 0, 0], [0, 0, 1], [0, 1, 0], ..., [1, 1, 1]]), we would have:

> getMFaces(1, 3, vertices)
> [
    [[0, 0, 0], [0, 0, 1]],
    [[0, 1, 0], [0, 1, 1]],
    [[0, 0, 0], [0, 1, 0]],
    [[0, 0, 1], [0, 1, 1]],
    [[1, 0, 0], [1, 0, 1]],
    [[1, 1, 0], [1, 1, 1]],
    [[1, 0, 0], [1, 1, 0]],
    [[1, 0, 1], [1, 1, 1]],
    [[0, 0, 0], [1, 0, 0]],
    [[0, 0, 1], [1, 0, 1]],
    [[0, 1, 0], [1, 1, 0]],
    [[0, 1, 1], [1, 1, 1]]
  ]

Edges in a 2-dimensional hypercube (a face) would give:

> getMFaces(1, 2, vertices)
> [
    [[0, 0], [0, 1]],
    [[1, 0], [1, 1]],
    [[0, 0], [1, 0]],
    [[0, 1], [1, 1]]
  ]

Faces (2-faces) in a cube would give:

> getMFaces(2, 3, vertices)
> [
    [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1]],
    [[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]],
    [[0, 0, 0], [0, 0, 1], [1, 0, 0], [1, 0, 1]],
    [[0, 1, 0], [0, 1, 1], [1, 1, 0], [1, 1, 1]],
    [[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]],
    [[0, 0, 1], [0, 1, 1], [1, 0, 1], [1, 1, 1]],
  ]

Note that a face is not an array of edge arrays, instead an array of the vertices that represent the face. Same goes for cels and any other n-face, i.e. an n-face is represented by a length 2^n array of vertices.

Using Hamming Distance

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. If a combination of 2^m vertices differ by exactly m bits, then they form an m-face.

For example, [0, 0, 0] and [0, 0, 1] form an edge (1-face) because they differ by 1 bit.

[0, 0, 0], [0, 0, 1], [0, 1, 0], and [0, 1, 1] form a face (2-face) because they differ by 2 bits (i.e. 1 bit is shared by all three vertices).

My algorithm produced lists of m-faces by recursively building combinations of vertices. Each time a vertex was added to the combination, the hamming distance would be checked between all vertices in the combination. If the hamming distance was > m, the combination would be ignored, otherwise we would continue building the combination until it contained 2^m vertices. If it did, and the hamming distance was exactly m, it would be added to the m-face list. This would continue until all combinations had been checked.

The problem with this algorithm is that it's extremely inefficient. The number of combinations that need to be checked get exponentially larger as the dimension n of the hypercube increases. Once I started building m-face lists for dimensions 9 and above the algorithm would take 30 seconds, 1 minute, 5 minutes, etc. to finish.

Looking for Patterns

I figured that, because the array of vertices provided was always ordered, there must be some pattern that forms as n and/or m increase. Using this pattern, I should be able to come up with a new algorithm that didn't depend on building combinations.

To visualize this relationship between n and m, I threw ordered vertices in a spreadsheet and colored in cells to represent m-faces. I started by looking at edges only:

Edges when n = 1, 2, 3, & 4

Right away I noticed a few patterns

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

m=1, n=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=2 n=1-4

m = 3 for dimensions 1 - 4

enter image description here

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!

Update

For anyone wondering, here is the function I've written using the logic described in Matt Timmermans answer:

// Utility function that converts a decimal number to a padded binary string
const getBinaryStr = (n, padding = 0) => (new Array(padding).fill("0").join("") + (n >>> 0).toString(2)).slice(-padding);

// Utility function that inserts a character into index ind of string str
const insertIntoStr = (char, str, ind) => `${str.slice(0, ind)}${char}${str.slice(ind)}`;

// Utility function that gets all n-length combinations of elements in arr
const getCombinations = (n, arr) => (arr.length === n) ? [arr] : (n === 0) ? [[]] : [...getCombinations(n-1, arr.slice(1), true).map(c => [arr[0], ...c]), ...getCombinations(n, arr.slice(1), true)];

// Returns a list of m-faces of an n-dimensional hypercube
const generateMFaces = (m, n) => {
    if (m > n) return [];

    // An m-face has m free bits and n - m fixed bits
    const free = m;
    const fixed = n - m;

    // Generate all combinations of n - m fixed bit indices
    const fixedIndices = getCombinations(fixed, Object.keys(new Array(n).fill(true)));

    const faces = [];
    // Select the indexes to fix
    for (let i = 0; i < fixedIndices.length; i++) {
        // Count in binary over the fixed bits
        for (let j = 0; j < 2**(n - m); j++) {
            const fixedBits = getBinaryStr(j, fixed);
            const face = [];
            // Count in binary over the free bits
            for (let k = 0; k < 2**m; k++) {
                let bitCode = getBinaryStr(k, free);
                // Insert fixed bits into their propper indexes
                for (let h = 0; h < fixed; h++) {
                    bitCode = insertIntoStr(fixedBits[h], bitCode, parseInt(fixedIndices[i][h]));
                }
                face.push(bitCode);
            }
            faces.push(face);
        }
    }
    return faces;
}

console.log(generateMFaces(1, 2));
console.log(generateMFaces(2, 3));
console.log(generateMFaces(3, 3));
console.log(generateMFaces(4, 3));
console.log(generateMFaces(4, 8).length);
console.log(generateMFaces(3, 12).length);

Solution

  • 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 2m combinations of the m coordinates in the m free dimensions, while holding the coordinates for the other dimensions fixed. Each of the 2n-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) * 2n-m faces overall.

    The number of edges in a cube, for example = C(3,1) * 22 = 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: