枚举在2D平面网格点降序排列（X * Y） [英] Enumerate grid points on 2D plane with descending order of (x * y)

问题描述

由于 N'GT; 0 和 M＆GT; 0 ，我要列举所有的（X，Y）对这样1 LT; = X＆LT; = N和1＆LT; = Y＆LT; = M的递减顺序（X * Y） 。 一个例子：指定N = 3和M = 2，则枚举序列应该是：

Given N > 0 and M > 0, I want to enumerate all (x, y) pairs such that 1 <= x <= N and 1 <= y <= M in descending order of (x * y). An example: given N = 3 and M = 2, the enumeration sequence should be:

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）可以互换。一个显而易见的方法是将全部列出来，插入到矢量＆lt;对＆LT; INT，INT＆GT; ＆GT; ，并调用的std ::排序（）用我自己的比较函数。然而，由于N和M可能很大，而且大部分时间我只需要序列的前几个方面，希望可以有一些更聪明的方式，产生这样的序列，而不是生成它们全和排序，其中需要多达 N * M 数组元素。

The order of (2, 1) and (1, 2) could be swapped. One obvious way is to list them all, insert into a vector<pair<int, int> >, and call std::sort() with my own comparison function. However, since N and M may be large, and most of the time I only need the first few terms of the sequence, I hope there could be some smarter way that generates such a sequence instead of generate them all-and-sort, which requires as many as N*M array elements.

更新：我忘了提及的是，虽然大部分时间我只需要前几个条款，要求项数为统计前未知

Update: I forgot to mention that although most of the time I only need the first few terms, the number of terms required is unknown before enumeration.

推荐答案

如果你只是希望以节省空间，同时保留时间相差无几，你可以在一个事实，即每个依次更小的元素必须是数相邻（在2-D网格你提到的），你已经遇到的要素之一。 （你可以用归纳法证明这一点，它不是特别困难。我要去承担这个是M> = N的其余部分。）

If you're just looking to save on space while retaining the time as more or less equal, you can count on the fact that each successively smaller element must be adjacent (in the 2-D grid you alluded to) to one of the elements you've already encountered. (You can prove this with induction, it's not particularly difficult. I'm going to assume for the rest of this that M>=N.)

基本算法看起来是这样的：

The basic algorithm looks something like:

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数（M + N）），其中k是你想要的点数。

You can repeat this as long as you want more elements in Enumerated Points. The max size of Candidates should be M+N so I think this is O(k log(M+N)) where k is the number of points you want.

附录： 避免重复的事情并不完全是困难的，但值得一提的。我将承担在此算法中，你把你的格掉，这样的数字会下降，你向下移动，右。无论如何，它是这样的：

ADDENDUM: The matter of avoiding duplicate is not entirely difficult but is worth mentioning. I will assume in this algo that you lay your grid out so that numbers go down as you move down and right. Anyway, it goes like this:

目前的算法开始创建一个数组（柱尺寸），其具有用于每个列的一个元素。应使此阵列包含在每列中这是列举的点的列表的一部分的行数

At the beginning of the algorithm create an array (Column Size) which has one element for each column. You should make this array contain the number of rows in each column which are part of the list of enumerated points.

在添加新元素和更新这个数组，你会检查列的大小两侧，以决定是否方格眼前的权利，这种新的枚举点以下已经在候选人名单

After you add a new element and update this array, you will check the size of the column on either side in order to decide if the grid squares to the immediate right and below of this new enumerated point are already in the candidates list.

检查列，如果它是一个比这更大左的大小，你不需要在下面添加新的枚举点的元素。

Check the size of the column to the left- if it's larger than this one, you don't need to add the element below your new enumerated point.

检查列的大小到右如果是比此列的同样大小的一个都不能少，你并不需要更新的元素添加到一个合适的。

Check the size of the column to the right- if it's one less than the same size of this column, you don't need to update the element to the right of this one.

为使这一显而易见的，让我们来看看这部分完成的图表，M = 4，N = 2：

To make this obvious, let's look at this partially completed chart for M=4, N=2:

4  3  2  1
*  *  *  2 |2
*  3  2  1 |1

的元素（4,2），（3,2），（2,2）和（4,1）是已在列表。 （第一坐标是M时，第二是N.）的列大小的数组为[2 1 1 0]，因为这是在每个当前正在使用列举的点列表列项的数目。我们将要添加（3,1）到新的列表 - 我们可以看到列大小到右边，得出这样的结论加入（2,1）是不需要的，因为对于该柱的尺寸M = 2是放大比1-1。其理由是pretty的清晰的视觉 - 我们已经增加（2,1）时，我们增加了（2,2）

The elements (4,2), (3,2), (2,2) and (4,1) are already in the list. (The first coordinate is M, the second is N.) The Column Size array is [2 1 1 0] since this is the number of items in each column that are in the Enumerated Points list. We are about to add (3,1) to the new list- We can look to the column size to the right and conclude that adding (2,1) isn't needed because the size of the column for M=2 is larger than 1-1. The reasoning is pretty clear visually - we already added (2,1) when we added (2,2).

这篇关于枚举在2D平面网格点降序排列（X * Y）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！