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