我正在尝试设计一种算法，给定n, m, and vertices (where n= 超立方体的维数，m= 我们尝试生成的面的尺寸，以及vertices is an ordered中的顶点列表n维超立方体），返回表示 m 面的顶点数组的数组n维超立方体 https://en.wikipedia.org/wiki/Hypercube.
这可能是一种令人困惑的措辞方式，所以这里有一些例子：
假设我们想要获取立方体（3 维超立方体）中的边数组（1 面）。如果我们假设vertices是立方体中顶点的二进制表示的有序数组（即[[0, 0, 0], [0, 0, 1], [0, 1, 0], ..., [1, 1, 1]]）， 我们会有：
> 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]]
]
二维超立方体（面）中的边将给出：
> getMFaces(1, 2, vertices)
> [
[[0, 0], [0, 1]],
[[1, 0], [1, 1]],
[[0, 0], [1, 0]],
[[0, 1], [1, 1]]
]
立方体中的面（2 个面）将给出：
> 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]],
]
请注意，面不是边数组的数组，而是表示面的顶点的数组。对于 cel 和任何其他 n 面也是如此，即 n 面由长度表示2^n顶点数组。
使用汉明距离
一种解决方案（我目前正在使用）是使用汉明距离 https://en.wikipedia.org/wiki/Hamming_distance顶点的二进制表示之间的比较以确定它们是否是 m 面的一部分。如果组合2^m顶点完全不同m位，然后它们形成一个 m 面。
例如，[0, 0, 0] and [0, 0, 1]形成一条边（1-面），因为它们相差 1 位。
[0, 0, 0], [0, 0, 1], [0, 1, 0], and [0, 1, 1]形成一个面（2-face），因为它们相差 2 位（即所有三个顶点共享 1 位）。
我的算法生成了以下列表m-通过递归构建顶点组合来构建面。每次将顶点添加到组合中时，都会检查组合中所有顶点之间的汉明距离。如果汉明距离 >m，该组合将被忽略，否则我们将继续构建该组合，直到它包含2^m顶点。如果是的话，汉明距离恰好是m，它将被添加到m- 面孔列表。这将持续下去，直到检查完所有组合为止。
该算法的问题在于效率极低。需要检查的组合数量随着维度呈指数级增长n超立方体的增加。一旦我开始构建维度 9 及以上的 m 面列表，算法将需要 30 秒、1 分钟、5 分钟等才能完成。
寻找模式
我想，因为提供的顶点数组总是有序的，所以一定有某种模式形成为n and/or m增加。使用这种模式，我应该能够想出一种不依赖于构建组合的新算法。
为了可视化之间的关系n and m，我将有序的顶点放入电子表格中，并在单元格中着色以表示 m 面。我首先只查看边缘：
我立刻注意到一些模式
- 有
n顶点索引之间不同大小的间隙
- The
i差距是2^i
然后我注意到维度的边缘列表n基于维度的边缘列表构建n-1递归地。这是有道理的，因为 n-超立方体几何结构是基于 n-1-超立方体几何结构构建的。
使用递归
我重新排列了我的电子表格并制作了表格n = 1..4 and m = 1..3:
m = 1适用于尺寸 1 - 4
Here, v表示顶点的有序数组，a表示输出的 m 面数组，每一列代表一个 m 面，彩色轮廓显示与较低维度的 m 面列表的关系（与较低维度的递归关系）。
黑色方块中的数字代表顶点的索引v.
我能够使用我注意到的模式推导出以下递归算法（其中m = 1是脸部的尺寸，n是超立方体的维数）。它不生成顶点数组，而是生成索引数组i代表的是i顶点：
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];
}
}
该算法成功地生成了维度的边列表n and is much比必须检查所有可能的顶点组合（如使用汉明距离时的情况）更有效。
缺点是该算法会生成索引，因此您必须随后将索引映射到实际顶点。它几乎立即生成维度高达 14 或 15 的边缘列表。
然后我做了床单m = 2 and m = 3（面孔和细胞）看看我是否可以绘制任何类型的连接并扩展我的递归算法以适用于所有人ms:
m = 2适用于尺寸 1 - 4
m = 3适用于尺寸 1 - 4
这就是我被困住的地方
我可以看出有某种模式贯穿于所有ms，我只是对精确定位并将其转化为算法的任务感到不知所措。
我可以告诉你m- 面孔列表m > 1以与我提供的递归算法类似的方式构建m = 1，我只是无法弄清楚需要添加什么。
对于这篇又长又令人困惑的帖子，我深表歉意。正如您可能从我对可视化的需求中看出的那样，我不太擅长线性代数，因此可能有一些明显的数学原理或我遗漏的东西。
对此算法的任何想法或帮助将不胜感激。我试图使其尽可能高效——也许使用循环实现它会比递归更有效，但我只是想在尝试提高效率之前获得一个工作算法。
由于这是我的第一篇文章，我不能 100% 确定我是否在正确的位置发布了这个问题，所以如果我在错误的论坛中，请告诉我。我可以看到这类问题可能更适合更多以算法或数学为中心的论坛，所以请告诉我是否有更好的地方可以发布此问题！
Update
对于任何想知道的人，这是我使用中描述的逻辑编写的函数马特·蒂默曼的回答 https://stackoverflow.com/a/71256888/12264298:
// 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);
