给定N > 0and M > 0，我想枚举所有 (x, y) 对，使得 1 <= x <= N 和 1 <= y <= M 按 (x * y) 的降序排列。一个例子：给定 N = 3 和 M = 2，枚举序列应该是：
1. (3, 2) -- 3 * 2 = 6
2. (2, 2) -- 2 * 2 = 4
3. (3, 1) -- 3 * 1 = 3
4. (2, 1) -- 2 * 1 = 2
5. (1, 2) -- 1 * 2 = 2
6. (1, 1) -- 1 * 1 = 1
(2, 1)和的顺序(1, 2)可以互换。一种明显的方法是将它们全部列出，插入到 avector<pair<int, int> >中，然后std::sort()用我自己的比较函数调用。但是，由于 N 和 M 可能很大，而且大多数时候我只需要序列的前几项，我希望可以有一些更聪明的方法来生成这样的序列，而不是生成它们全部排序，这需要尽可能多的N*M数组元素。
更新：我忘了提到虽然大多数时候我只需要前几个词，但在枚举之前需要的词数是未知的。
如果您只是想节省空间，同时保持时间大致相等，您可以指望每个连续较小的元素必须与其中一个元素相邻（在您提到的二维网格中）你已经遇到过。（你可以用归纳法证明这一点，这并不是特别困难。我将假设其余部分 M>=N。）
基本算法看起来像：
Start with a list (Enumerated Points) containing just the maximum element, M*N
Create a max heap (Candidates) containing (M-1),N and M,(N-1).
Repeat this:
1.Pick the largest value (x,y) in Candidates and append it to Enumerated Points
2.Add (x-1),y and x,(y-1) to Candidates if they are not there already
只要您想要枚举点中的更多元素，您就可以重复此操作。候选人的最大大小应该是 M+N 所以我认为这是 O(k log(M+N)) 其中 k 是你想要的点数。
附录：避免重复的事情并不完全困难，但值得一提。我会在这个算法中假设你把你的网格布置好，这样当你向下和向右移动时数字会下降。无论如何，它是这样的：
在算法开始时，创建一个数组（列大小），其中每一列都有一个元素。您应该使此数组包含每列中的行数，这些行数是枚举点列表的一部分。
添加新元素并更新此数组后，您将检查任一侧列的大小，以确定此新枚举点右侧和下方的网格正方形是否已在候选列表中。
检查左侧列的大小 - 如果它大于此列，则无需在新枚举点下方添加元素。
检查右侧列的大小 - 如果它比此列的相同大小小一，则无需更新此列右侧的元素。
为了清楚起见，让我们看一下 M=4，N=2 的这个部分完成的图表：
4 3 2 1
* * * 2 |2
* 3 2 1 |1
元素 (4,2)、(3,2)、(2,2) 和 (4,1) 已经在列表中。（第一个坐标是 M，第二个是 N。） Column Size 数组是 [2 1 1 0]，因为这是 Enumerated Points 列表中每列中的项目数。我们即将将 (3,1) 添加到新列表中 - 我们可以查看右侧的列大小并得出不需要添加 (2,1) 的结论，因为 M=2 的列大小更大比 1-1。推理在视觉上非常清楚 - 我们在添加 (2,2) 时已经添加了 (2,1)。
这是一个 O(K logK) 解决方案，其中 K 是您要生成的术语数。
编辑：Q 只保留每个元素的一份副本；如果元素已经存在，则插入失败。
priority_queue Q
Q.insert( (N*M, (N,M)) ) // priority, (x,y)
repeat K times:
(v, (x,y)) = Q.extract_max()
print(v, (x,y))
Q.insert( (x-1)*y, (x-1,y) )
Q.insert( x*(y-1), (x,y-1) )
这是因为在访问 (x,y) 之前，您必须访问 (x+1,y) 或 (x,y+1)。复杂度为 O(KlogK)，因为 Q 最多有 2K 个元素被推入其中。
这实际上等同于枚举素数；您想要的数字是所有不是素数的数字（所有具有x或y等于 1 的数字除外）。
我不确定是否有一种枚举素数的方法会比您已经提出的更快（至少在算法复杂性方面）。
因为您提到大多数时候您需要序列的前几个项；在生成它们之后，您不需要对它们全部进行排序以找到这些前几个术语。您可以根据所需的术语数量使用最大堆，例如 k。因此，如果堆的大小为 k (<< N && << M)，那么您可以在 nlogk 之后拥有最大的 k 项，这比 nlogn 更适合排序。
这里 n = N*M
一种从 NxM 循环到 1 的虚拟方法，搜索相乘时产生当前数字的对：
#!/usr/bin/perl
my $n = 5;
my $m = 4;
for (my $p = $n * $m; $p > 0; $p--) {
my $min_x = int(($p + $m - 1) / $m);
for my $x ($min_x..$n) {
if ($p % $x == 0) {
my $y = $p / $x;
print("x: $x, y: $y, p: $p\n");
}
}
}
对于 N=M，复杂度为 O(N 3 )，但内存使用量为 O(1)。
更新：请注意，复杂性并不像看起来那么糟糕，因为要生成的元素数量已经是 N 2。为了比较，生成所有对和排序方法是 O(N 2 logN) 与 O(N 2 ) 内存使用。
这是给你的算法。我会尽量给你一个英文描述。
在我们正在使用的矩形中，我们总是可以假设一个点P(x, y)的“面积”大于它下面的点P(x, y-1)。所以在寻找最大面积的点时，我们只需要比较每列中最顶部的未取点（即每个可能的点x）。例如，当考虑原始3 x 5网格时
5 a b c
4 d e f
3 g h i
2 j k l
1 m n o
1 2 3
我们真的只需要比较a,b和c。保证所有其他点的面积都小于其中至少一个点的面积。所以构建一个最大堆，它只包含每列中的最高点。当您从堆中弹出一个点时，将其正下方的点推入（如果该点存在）。重复直到堆为空。这为您提供了以下算法（经过测试，但它在 Ruby 中）：
def enumerate(n, m)
heap = MaxHeap.new
n.times {|i| heap.push(Point.new(i+1, m))}
until(heap.empty?)
max = heap.pop
puts "#{max} : #{max.area}"
if(max.y > 1)
max.y -= 1
heap.push(max)
end
end
end
这给你一个运行时间O((2k + N) log N)。堆操作成本log N；我们N在构建初始堆时使用它们，然后2k当我们拉出k最大面积的点时（假设每个弹出点之后是在它下面的点的推送）。
它的另一个优点是不必构建所有点，这与构建整个集合然后排序的原始建议不同。您只需构建尽可能多的点以保持堆准确。
最后： 可以进行改进！ 我没有做过这些，但你可以通过以下调整获得更好的性能：
y = x每一列而不是y = 1. 要生成不再检查的点，请使用 的面积P(x, y)等于 的面积这一事实P(y, x)。 注意：如果使用此方法，则需要两个版本的算法。列在 时有效M >= N，但如果M < N您需要按行执行此操作。a从一开始就包含在堆中，因为它保证小于b. 所以你只需要在相邻列的顶点被弹出时将列添加到堆中。这变成了一篇小论文......无论如何 - 希望它有所帮助！
编辑： 完整的算法，结合了我上面提到的两项改进（但仍然在 Ruby 中，因为我很懒）。请注意，不需要任何额外的结构来避免插入重复项 - 除非它是“顶部”点，否则每个点只会在其行/列中插入另一个点。
def enumerate(n, m, k)
heap = MaxHeap.new
heap.push(Point.new(n, m))
result = []
loop do
max = heap.pop
result << max
return result if result.length == k
result << Point.new(max.y, max.x) if max.x <= m && max.y <= n && max.x != max.y
return result if result.length == k
if(m < n) # One point per row
heap.push(Point.new(max.x, max.y - 1)) if max.x == n && max.y > 1
heap.push(Point.new(max.x - 1, max.y)) if max.x > max.y
else # One point per column
heap.push(Point.new(max.x - 1, max.y)) if max.y == m && max.x > 1
heap.push(Point.new(max.x, max.y - 1)) if max.y > max.x
end
end
end
我得到了它！
将网格视为一组 M 列，其中每一列都是一个堆栈，其中包含从底部的 1 到顶部的 N 的元素。每列都标有其 x 坐标。
每个列堆栈中的元素都按其 y 值排序，因此也按 x*y 排序，因为 x 对所有这些元素都具有相同的值。
因此，您只需要选择顶部具有较大 x*y 值的堆栈，将其弹出并重复。
实际上，您不需要堆栈，只需要顶部值的索引，您可以使用优先级队列来获取具有较大 x*y 值的列。然后，递减索引的值，如果它大于 0（表示堆栈尚未耗尽），则将堆栈重新插入队列中，并以其新的优先级 x*y。
对于 N=M，该算法的复杂度为 O(N 2 logN)，其内存使用量为 O(N)。
更新：在 Perl 中实现...
use Heap::Simple;
my ($m, $n) = @ARGV;
my $h = Heap::Simple->new(order => '>', elements => [Hash => 'xy']);
# The elements in the heap are hashes and the priority is in the slot 'xy':
for my $x (1..$m) {
$h->insert({ x => $x, y => $n, xy => $x * $n });
}
while (defined (my $col = $h->extract_first)) {
print "x: $col->{x}, y: $col->{y}, xy: $col->{xy}\n";
if (--$col->{y}) {
$col->{xy} = $col->{x} * $col->{y};
$h->insert($col);
}
}
在 Haskell 中，它立即产生输出。这是一个插图：
-------
-*------
-**------
-***------
-****------
-*****------
-******------
-*******------
每个星号点都会产生 (x,y) 和 (y,x)。该算法从右上角“吃掉”这个东西，比较每一列中的顶部元素。边界的长度永远不会超过N（我们假设N >= M）。
enuNM n m | n<m = enuNM m n -- make sure N >= M
enuNM n m = let
b = [ [ (x*y,(x,y)) | y<- [m,m-1..1]] | x<-[n,n-1..m+1]]
a = [ (x*x,(x,x)) :
concat [ [(z,(x,y)),(z,(y,x))] -- two symmetrical pairs,
| y<- [x-1,x-2..1] -- below and above the diagonal
, let z=x*y ] | x<-[m,m-1..1]]
in
foldi (\(x:xs) ys-> x : merge xs ys) [] (b ++ a)
merge a@(x:xs) b@(y:ys) = if (fst y) > (fst x)
then y : merge a ys
else x : merge xs b
merge a [] = a
merge [] b = b
foldi f z [] = z
foldi f z (x:xs) = f x (foldi f z (pairs f xs))
pairs f (x:y:t) = f x y : pairs f t
pairs f t = t
foldi构建一个倾斜的无限加深的树作为一个堆，连接所有的生产者流，每个生产者流，每个生产者流x已经按降序排序。由于生产者流的所有初始值都保证按降序排列，因此每个初始值都可以在不进行比较的情况下弹出，从而可以懒惰地构建树。
的代码a使用对角线下方的相应对生成对角线上方的对（在假设下N >= M，对于每个(x,y)where x <= M & y < x，(y,x)也将生成。）
对于非常接近比较树顶部的少数第一个值中的每一个，它实际上应该是 O(1)。
Prelude Main> 取 10 $ 地图 snd $ enuNM (2000) (3000) [(3000,2000),(2999,2000),(3000,1999),(2998,2000),(2999,1999),(3000,1998),(2997,2 000),(2998,1999),(2999,1998),(2996,2000)] （0.01 秒，1045144 字节） Prelude Main> let xs=take 10 $map (log.fromIntegral.fst) $ enuNM (2000) (3000) Prelude Main> zipWith (>=) xs (tail xs) [True,True,True,True,True,True,True,True,True] Prelude Main> 取 10 $ map snd $ enuNM (2*10^8) (3*10^8) [(300000000,200000000),(299999999,200000000),(300000000,199999999),(299999998,20 0000000),(299999999,199999999),(300000000,199999998),(299999997,200000000),(2999 99998,199999999),(299999999,199999998),(299999996,200000000)] （0.01 秒，2094232 字节）
我们可以评估经验运行时复杂度：
Prelude Main> take 10 $ drop 50000 $ map (log.fromIntegral.fst) $ enuNM (2*10^8) (3*10^8) [38.633119670465554,38.633119670465554,38.63311967046555,38.63311967046554,38.63 311967046554,38.63311967046553,38.63311967046553,38.633119670465526,38.633119670 465526,38.63311967046552] （0.17 秒，35425848 字节） Prelude Main> take 10 $ drop 100000 $ map (log.fromIntegral.fst) $ enuNM (2*10^8 ) (3*10^8) [38.63311913546512,38.633119135465115,38.633119135465115,38.63311913546511,38.63 311913546511,38.6331191354651,38.6331191354651,38.633119135465094,38.63311913546 5094,38.63311913546509] （0.36 秒，71346352 字节） *Main> 让 x=it *Main> zipWith (>=) x (tail x) [True,True,True,True,True,True,True,True,True] Prelude Main> logBase 2 (0.36/0.17) 1.082462160191973 -- O(n^1.08) 产生 n=100000 个值
这可以以一种简单的方式翻译成 Python，例如使用 Haskell 流的生成器，如这里所示。