有什么快速的方法可以生成按其乘积排序的笛卡尔坐标对吗？

Question

我想在一个有界正方形内生成笛卡尔坐标对，这些正方形按乘积降序排列。例如，对于大小为 3 的正方形，坐标为：

(3,3), (3,2), (2,3), (2,2), (3,1), (1,3), (2,1), (1,2), (1,1)

有什么方法可以快速生成此列表 - 即，将整数映射到第 n 个坐标的恒定时间函数？

Answer 1

也许您可以根据您希望多快的生成速度以及多快的速度改变正方形的边界来详细说明您的具体需求。

这个问题类似于在乘法中生成不同的数字 table（Paul Erdos 研究了基数，已知最快的精确计算算法是 O(n^2)）。

考虑生成列表部分（假设您不会列出数十亿个坐标）的一种方法是按降序快速散列部分 i*j 集并对其进行排序。为了使散列准确，我们将其扩展到所选范围 [n,k] 以下，直到 n * l 低于 k*k 对于某些 l。例如，对于从 (10,10) 到 (7,7) 的坐标范围，我们将散列扩展到 (5,5)，这样大于 (7,7) 的 (10,5) 将被包括在内。

JavaScript代码：

function f(n,k){
  var l = k, k2 = k*k;
  while (n*l > k2){
    l--;
  }
  console.log("low bound: " + l);
  var h = {}, h2 = [];
  for (var i=n; i>l; i--){
    for (var j=i; j>l; j--){
      var m = i*j;
       if (h[m]) h[m] = h[m].concat([i,j]);
       else {
         h[m] = [i,j];
         h2.push(m);
      }
    }
  }
  h2.sort(function(a,b){return b-a});
  var i=0;
  while(h2[i] >= k2){
    console.log(h[h2[i++]]);
  }
}

输出：

f(10,6)

low bound: 3

(10,10) 
(10,9) 
(9,9) 
(10,8)
...
(10,4), (8,5)
(9,4), (6,6)

更多输出：

f(1000000,999995)

low bound: 999990

(1000000,1000000) 
(1000000,999999) 
(999999,999999)
(1000000,999998) 
(999999,999998) 
(1000000,999997) 
(999998,999998) 
(999999,999997) 
(1000000,999996) 
(999998,999997)
(999999,999996) 
(1000000,999995) 
(999997,999997)
(999998,999996)
(999999,999995) 
(1000000,999994)
(999997,999996) 
(999998,999995) 
(999999,999994) 
(1000000,999993) 
(999996,999996)
(999997,999995) 
(999998,999994) 
(999999,999993) 
(1000000,999992) 
(999996,999995) 
(999997,999994) 
(999998,999993) 
(999999,999992) 
(1000000,999991) 
(999995,999995)

Answer 2

我没有测试过这个想法。您可以通过从右下角到左上角去除对角线来快速生成大致正确顺序的所有坐标列表，就像 countability of the rationals 的参数一样。这会给你一个几乎排序的列表。

有一些排序方法可以利用它来加快排序速度。有关讨论，请参阅 Which sorting algorithm is best suited to re-sort an almost fully sorted list?。您可以随时尝试不同的排序算法，看看哪种算法最适合您的数据。

Answer 3

您的枚举应该自然地从 top-right 角进行到 bottom-left。

维护边界作为优先队列。从右上角开始，边界中只有一个条目。

在每一步中，从 PQ 中弹出最大元素并将其三个后代（West、South 和 South-West）插入队列，而不创建重复项_{（可能使用实际数组支持队列的数组，但这意味着额外的 space...好吧，这些短（比如说，垂直）数组不超过 n，每个不超过几个元素，并且他们从不grow/move向上，只向下)。}

队列长度为 O(n) – 认为 "diagonals", even if curved, –

并产生 n² 结果，因此总体复杂度取决于队列实现的效率。如果这是对数的，它将是 O(n² log n) 如果是线性的（使用散列 table，我们知道涉及的值的范围），O(n²)，整体；但它将是 on-line, – O(1)...O(log n)[=每对生产 55=]。

如果精度允许（对于您的范围，它看起来会），预先计算坐标的对数，并按 log(x) + log(y) 而不是按x * y，交易 O(n²) 乘法 n 对数和 O(n²)个加法。

编辑： 见 this 另一个非常相似的算法的实际 Haskell 代码；它还包含额外的提示，说明如何将速度提高 2 倍 (xy==yx)，因此只在正方形的三角形一半上工作——这也会将所需的 space 减半。而且好像不需要把SWchild加入优先级队列，只需要S和W就够了！

有什么快速的方法可以生成按其乘积排序的笛卡尔坐标对吗？

Is there any fast way to generate the pairs of cartesian coordinates ordered by their product?

algorithm

language-agnostic