生成边长和对角线均为整数的长方体：如何提高时间复杂度？

Question

我快速编写了这段代码来测试长方体 a、b、c、d、e 和 f 的所有边和对角线是否均为整数。它似乎工作得很好，但循环越来越高的值需要太多时间（例如 10000+）。

有什么方法可以让这段代码运行得更快吗？或者也许以某种方式摆脱那个令人讨厌的三个嵌套 for 循环？

我想了一些方法来降低这段代码的复杂性，但它并没有经历所有组合，这是我想要发生的事情。

const generate_good_cuboid = () => {
  let good_couples = [];
  let couples = [];
  for (let a = 1; a < 10000; a++) {
    for (let b = 1; b < 10000; b++) {
      for (let c = 1; c < 10000; c++) {
        let e_squared = Math.pow(a, 2) + Math.pow(c, 2);
        let e = Math.sqrt(e_squared);
        if (Number.isInteger(e)) {
          let d_squared = Math.pow(a, 2) + Math.pow(b, 2);
          let d = Math.sqrt(d_squared);
          if (Number.isInteger(d)) {
            let f_squared = Math.pow(b, 2) + Math.pow(c, 2);
            let f = Math.sqrt(f_squared);
            if (Number.isInteger(f)) {
              good_couples.push({ a, b, c, d, e, f });
            }
          }
        }
      }
    }
  }
  return couples;
};


console.log(generate_good_cuboid());

Answer 1

这里有一个解决方案，使用原始毕达哥拉斯三元树来生成所有最大元素小于您的极限的毕达哥拉斯三元组。

然后它创建一个图（邻接表），其中一个整数与另一个整数有链接，如果它们是毕达哥拉斯三元组中较小的两个成员。

最后它检查是否可以将它们组合成所需的 a、b 和 c 组合：

function* pythagorianTriples(limit) {
    const ABC = [
        [[1, -2, 2], [2, -1, 2], [2, -2, 3]],
        [[1,  2, 2], [2,  1, 2], [2,  2, 3]],
        [[-1, 2, 2], [-2, 1, 2], [-2, 2, 3]]
    ]
    let triples = [[3, 4, 5]];
    while (triples.length) {
        const children = [];
        for (const triple of triples) {
            const sorted = triple.toSorted((a, b) => a - b);
            if (sorted[2] >= limit) continue;
            const maxCoeff = Math.floor(limit / sorted[2]);
            // Yield multiples of this primitive pythagorian triple
            for (let i = 1; i <= maxCoeff; i++) {
                yield [sorted[0] * i, sorted[1] * i, sorted[2] * i];
            }
            // Get the triple's three children in the tree of Pythagorian triples:
            children.push(...ABC.map(mat =>
                mat.map(row => 
                    row[0] * triple[0] + row[1] * triple[1] + row[2] * triple[2]
                )
            ));
        }
        triples = children;
    }
}

function generateGoodCuboids(limit) {
    const pairSide = Array.from({length: limit}, (_, i) => new Set);
    const triples = [...pythagorianTriples(limit)];
    // Link pairs that belong to same Pythagorian triple; for fast lookup
    for (const [a, b] of triples) {
        pairSide[a].add(b);
        pairSide[b].add(a);
    }
    // Find valid combinations
    const solutions = [];
    for (const [a, b] of triples) {
        for (const c of pairSide[a]) {
            if (c >= b && pairSide[b].has(c)) solutions.push([a, b, c]);
        }
    }
    // For convenience, sort them:
    return solutions.sort(([a], [b]) => a - b);
}

const cuboids = generateGoodCuboids(1000);
console.log(`There are ${cuboids.length} solutions for sides < 1000:`);
for (const cuboid of cuboids) console.log(...cuboid);

// For 10 times more:
const cuboids2 = generateGoodCuboids(10000);
console.log(`There are ${cuboids2.length} solutions for sides < 10000`);

// For 10 times more:
const cuboids3 = generateGoodCuboids(100000);
console.log(`There are ${cuboids3.length} solutions for sides < 100000`);

当限制为 1000 时，脚本找到 8 个解（忽略排列）；它重复该工作 10000（128 个解决方案）和 100000（1457 个解决方案）。

Answer 2

一个简单的优化是计算

d

（从

a

和

b

）并在循环所有

c

之前检查其整数性。

此外，您可以通过将结果限制为

a=3, b=4

来避免生成重复项，例如

a=4, b=3

和

a < b < c

，并在需要所有解决方案时排列您的解决方案。然后你可以优化

for (let b = a; b < 10000; b++)

和

for (let c = b; c < 10000; c++)

（尽管这并没有真正改变复杂性）。

最后但并非最不重要的一点是，您可以预先生成所有已知良好的毕达哥拉斯三元组集（仅一次），然后搜索它们以找到共享一侧的两个三元组（三角形），并检查其他两条腿是否相同(catheti) 也构成勾股三元组。对于第一部分，使用任何已知算法（生成勾股三元组、原始勾股三元组树、高效查找所有勾股三元组、生成勾股三元组的最佳方法等）。

Answer 3

如果 a 和 b 边没有给出整数，则可以避免内部循环。您也可以使用更快的

(d|0) === d

。

const generate_good_cuboid = sz => {
  let good_couples = [];
  for (let a = 1; a < sz; a++) {
      for (let b = 1; b < sz; b++) {
          const d = Math.sqrt(a ** 2 + b ** 2);
          if ((d|0)===d) {
              for (let c = 1; c < sz; c++) {
                  const e = Math.sqrt(a ** 2 + c ** 2);
                  if ((e|0)===e) {
                      const f = Math.sqrt(b ** 2 + c ** 2);
                      if ((f|0)===f) {
                          good_couples.push({ a, b, c, d, e, f });
                      }
                  }
              }
          }
      }
  }

  return good_couples;
};

console.log(generate_good_cuboid(10000));