Enumerate grid points on 2D plane with descending order of (x * y)

Question

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

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.

Answer 1

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

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.

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

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).

Answer 2

Here's an O(K logK) solution, where K is the number of terms you want to generate.
Edit: Q keeps only one copy of each element; an insert fails if the element is already present.

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) )

This works because before visiting (x,y) you must visit either (x+1,y) or (x,y+1). The complexity is O(KlogK) since Q at most 2K elements are pushed into it.