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

Question

I want to generate the pairs of cartesian coordiantes inside a bounded square ordered by their product in descending order. For example, for a square of size 3, the coordinates are:

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

Is there any way to generate this list fast - i.e, a constant-time function that maps integers to the nth coordinate?

Answer 1

your enumeration should proceed from the top-right corner to the bottom-left, naturally.

maintain the boundary as a priority queue. start with top right corner being the only one entry in the boundary.

on each step, pop the max element from the PQ and insert its three descendants (West, South, and South-West) into the queue, without creating duplicates _{(maybe use actual array of arrays to back the queue, but that means additional space... well, there are no more than n of these short (say, vertical) arrays, each no larger than a few elements, and they never grow/move upwards, only downwards).}

Length of the queue is O(n) – think "diagonals", even if curved, –

and you produce n² results, so overall complexity depends on the efficiency of the queue implementation. If that's logarithmic, it'll be O(n² log n) and if linear (using hash table, as we know the range of the values involved), O(n²), overall; but it will be on-line, – O(1)...O(log n) per produced pair.

If the precision will allow (for your range it looks like it will), precalculate logarithms of your coordinates, and order the pairs by log(x) + log(y) instead of by x * y, trading O(n²) multiplications for n logarithms and O(n²) additions.

edit: see this for an actual Haskell code for another, very similar algorithm; it also contains additional hint how to speed it up by another factor of 2 (xy==yx), so work on a triangular half of the square only -- this will also halve the space needed. And it looks like there's no need to add the SW child to the priority queue, just S and W should be enough!

Answer 2

Perhaps you could elaborate more on your specific needs in terms of how fast you would like the generation and how rapidly you might change the bounds of the square.

This problem is akin to generating the distinct numbers in a multiplication table (the cardinality of which studied Paul Erdos and the fastest known algorithm to calculate exactly is O(n^2)).

One way to consider generating sections of your list (assuming you will not be listing billions of coordinates) is to quickly hash a partial set of i*js in descending order and sort them. To make the hash accurate, we extend it below the chosen range [n,k] until after n * l is lower than k*k for some l. For example, for the range of coordinates from (10,10) to (7,7), we extend our hash to (5,5) so that (10,5), which is greater than (7,7), will be included.

JavaScript code:

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++]]);
  }
}

Output:

f(10,6)

low bound: 3

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

More output:

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)