動態生成n維超立方體m面串列的演算法-有解無憂

我正在嘗試設計一種演算法，給定n,m和vertices(其中n= 超立方體m的維度, = 我們嘗試生成的面的維度, 并且vertices是一個-維超立方體中頂點的有序串列),回傳表示動態生成n維超立方體m面串列的演算法

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

動態生成n維超立方體m面串列的演算法

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

動態生成n維超立方體m面串列的演算法

`m = 3` for dimensions 1 - 4

動態生成n維超立方體m面串列的演算法

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

對于任何想知道的人，這是我使用Matt Timmermans 回答中描述的邏輯撰寫的函式：

// 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);