动态生成n维超立方体m面列表的算法
Algorithm to dynamically generate m-face list for n-dimensional hypercube
我正在尝试设计一种算法，给定 n、m 和 vertices（其中 n = 超立方体的维度，m = 我们试图生成的面的维度，vertices 是 有序 顶点列表 n 维超立方体）， returns 表示 n-dimensional hypercube.
中的 m 面的顶点数组数组
这可能是一种令人困惑的表达方式，所以这里有几个例子：
假设我们想要在一个立方体（3 维超立方体）中获得一组边（单面）。如果我们假设 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 的顶点数组表示。
使用汉明距离
一个解决方案（我目前正在使用）是使用顶点二进制表示之间的 hamming distance 来确定它们是否是 m 面的一部分。如果 2^m 个顶点的组合恰好相差 m 位，则它们形成一个 m 面。
例如，[0, 0, 0]和[0, 0, 1]形成一条边（1面），因为它们相差1位。
[0, 0, 0]、[0, 0, 1]、[0, 1, 0]、[0, 1, 1]形成一个面（2-face），因为它们相差2位（即1位被共享）所有三个顶点）。
我的算法通过递归构建顶点组合生成了 m 个面的列表。每次将一个顶点添加到组合中时，都会检查组合中所有顶点之间的汉明距离。如果汉明距离 > m，组合将被忽略，否则我们将继续构建组合，直到它包含 2^m 个顶点。如果是这样，并且汉明距离正好是 m，它将被添加到 m-face 列表中。这将一直持续到检查完所有组合为止。
这个算法的问题是效率极低。随着超立方体维度 n 的增加，需要检查的组合数量呈指数增长。一旦我开始构建维度 9 及以上的 m-face 列表，算法将需要 30 秒、1 分钟、5 分钟等才能完成。
寻找模式
我想，因为提供的顶点数组总是有序的，所以一定有一些模式随着 n and/or m 的增加而形成。使用这个模式，我应该能够想出一个不依赖于建筑组合的新算法。
为了可视化 n 和 m 之间的这种关系，我在电子表格中放置了有序的顶点，并在单元格中着色以表示 m 面。我开始只看边缘：
我马上注意到一些模式
- 顶点索引之间存在
n 个不同大小的间隙
- 第
i个差距是2^i
然后我注意到维度 n 的边列表递归地建立在维度 n-1 的边列表的基础上。这是有道理的，因为 n-超立方体几何建立在 n-1-超立方体几何之上。
使用递归
我重新整理了电子表格并为 n = 1..4 和 m = 1..3 制作了表格：
m = 1 对于维度 1 - 4
这里，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 的边列表，并且 比必须检查每个可能的顶点组合（就像使用汉明距离）。
缺点是该算法会生成索引，因此您必须在之后将索引映射到实际顶点。它几乎可以立即生成尺寸高达 14 或 15 的边列表。
然后我为 m = 2 和 m = 3（面孔和细胞）制作了表格，看看我是否可以绘制任何类型的连接并扩展我的递归算法以适用于所有 m小号：
m = 2 对于维度 1 - 4
m = 3 对于维度 1 - 4
这就是我卡住的地方
我可以看出有某种模式延伸到所有 ms，我只是不知所措地确定它并将其转化为算法的任务。
我可以看出 m > 1 的 m-face 列表的构建方式与我为 m = 1 提供的递归算法的构建方式类似，我只是无法理解找出需要添加的内容。
对于冗长、混乱的 post，我深表歉意。你可能会从我对可视化的需求看出，我不太擅长线性代数，所以可能有一些明显的数学原理或我遗漏的东西。
如果您对此算法有任何想法或帮助，我们将不胜感激。我试图让它尽可能高效——也许使用循环实现它比递归更有效，但我只是想在尝试提高效率之前获得一个工作算法。
因为这是我的第一个 post，我不能 100% 确定我是否 post 在正确的位置回答这个问题，所以请告诉我如果我在错误的论坛。我可以看出这类问题如何更适合算法或以数学为中心的论坛，所以让我知道是否有更好的地方 post 这个！
更新
对于任何想知道的人，这是我使用 :
中描述的逻辑编写的函数
// 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);
m 尺寸的每个 m 大小的子集都是 m[=35] 尺寸的“方向” =] 尺寸“自由”。对于每个方向，您可以通过在 m[=35] 中生成 m 坐标的所有 2m 组合来生成一个面=] 自由维度，同时保持其他维度的坐标固定。其他维度的2n-m个坐标组合中的每一个都是不同面的“位置”。
方向的数量是 C(n,m) = n!/m!(n-m)!, 所以你最终应该得到 C(n,m) * 2 n-m 整体面孔。
立方体的边数，例如= C(3,1) * 22 = 3 * 4 = 12.
立方体的面数是C(3,2) * 2 = 3 * 2 = 6。
生成所有面孔并不难：
- 对于每个方向，确定自由尺寸和固定尺寸
- 使用固定维度进行二进制计数以找到所有面部位置
- 对于每个面，在自由维度上以二进制计数以生成其顶点。
我正在尝试设计一种算法，给定 n、m 和 vertices（其中 n = 超立方体的维度，m = 我们试图生成的面的维度，vertices 是 有序 顶点列表 n 维超立方体）， returns 表示 n-dimensional hypercube.
这可能是一种令人困惑的表达方式，所以这里有几个例子：
假设我们想要在一个立方体（3 维超立方体）中获得一组边（单面）。如果我们假设 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 的顶点数组表示。
使用汉明距离
一个解决方案（我目前正在使用）是使用顶点二进制表示之间的 hamming distance 来确定它们是否是 m 面的一部分。如果 2^m 个顶点的组合恰好相差 m 位，则它们形成一个 m 面。
例如，[0, 0, 0]和[0, 0, 1]形成一条边（1面），因为它们相差1位。
[0, 0, 0]、[0, 0, 1]、[0, 1, 0]、[0, 1, 1]形成一个面（2-face），因为它们相差2位（即1位被共享）所有三个顶点）。
我的算法通过递归构建顶点组合生成了 m 个面的列表。每次将一个顶点添加到组合中时，都会检查组合中所有顶点之间的汉明距离。如果汉明距离 > m，组合将被忽略，否则我们将继续构建组合，直到它包含 2^m 个顶点。如果是这样，并且汉明距离正好是 m，它将被添加到 m-face 列表中。这将一直持续到检查完所有组合为止。
这个算法的问题是效率极低。随着超立方体维度 n 的增加，需要检查的组合数量呈指数增长。一旦我开始构建维度 9 及以上的 m-face 列表，算法将需要 30 秒、1 分钟、5 分钟等才能完成。
寻找模式
我想，因为提供的顶点数组总是有序的，所以一定有一些模式随着 n and/or m 的增加而形成。使用这个模式，我应该能够想出一个不依赖于建筑组合的新算法。
为了可视化 n 和 m 之间的这种关系，我在电子表格中放置了有序的顶点，并在单元格中着色以表示 m 面。我开始只看边缘：
我马上注意到一些模式
- 顶点索引之间存在
n个不同大小的间隙 - 第
i个差距是2^i
然后我注意到维度 n 的边列表递归地建立在维度 n-1 的边列表的基础上。这是有道理的，因为 n-超立方体几何建立在 n-1-超立方体几何之上。
使用递归
我重新整理了电子表格并为 n = 1..4 和 m = 1..3 制作了表格：
m = 1 对于维度 1 - 4
这里，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 的边列表，并且 比必须检查每个可能的顶点组合（就像使用汉明距离）。
缺点是该算法会生成索引，因此您必须在之后将索引映射到实际顶点。它几乎可以立即生成尺寸高达 14 或 15 的边列表。
然后我为 m = 2 和 m = 3（面孔和细胞）制作了表格，看看我是否可以绘制任何类型的连接并扩展我的递归算法以适用于所有 m小号：
m = 2 对于维度 1 - 4
m = 3 对于维度 1 - 4
这就是我卡住的地方
我可以看出有某种模式延伸到所有 ms，我只是不知所措地确定它并将其转化为算法的任务。
我可以看出 m > 1 的 m-face 列表的构建方式与我为 m = 1 提供的递归算法的构建方式类似，我只是无法理解找出需要添加的内容。
对于冗长、混乱的 post，我深表歉意。你可能会从我对可视化的需求看出，我不太擅长线性代数，所以可能有一些明显的数学原理或我遗漏的东西。
如果您对此算法有任何想法或帮助，我们将不胜感激。我试图让它尽可能高效——也许使用循环实现它比递归更有效，但我只是想在尝试提高效率之前获得一个工作算法。
因为这是我的第一个 post，我不能 100% 确定我是否 post 在正确的位置回答这个问题，所以请告诉我如果我在错误的论坛。我可以看出这类问题如何更适合算法或以数学为中心的论坛，所以让我知道是否有更好的地方 post 这个！
更新
对于任何想知道的人，这是我使用
// 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);
m 尺寸的每个 m 大小的子集都是 m[=35] 尺寸的“方向” =] 尺寸“自由”。对于每个方向，您可以通过在 m[=35] 中生成 m 坐标的所有 2m 组合来生成一个面=] 自由维度，同时保持其他维度的坐标固定。其他维度的2n-m个坐标组合中的每一个都是不同面的“位置”。
方向的数量是 C(n,m) = n!/m!(n-m)!, 所以你最终应该得到 C(n,m) * 2 n-m 整体面孔。
立方体的边数，例如= C(3,1) * 22 = 3 * 4 = 12.
立方体的面数是C(3,2) * 2 = 3 * 2 = 6。
生成所有面孔并不难：
- 对于每个方向，确定自由尺寸和固定尺寸
- 使用固定维度进行二进制计数以找到所有面部位置
- 对于每个面，在自由维度上以二进制计数以生成其顶点。
- 使用固定维度进行二进制计数以找到所有面部位置