Is there a quick way to generate pairs of Cartesian coordinates ordered by their product?

Question

I want to create pairs of Cartesian coordinators within a bounded square, ordered by their product in descending order. For example, for a square of size 3 coordinates:

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

Is there a way to quickly generate this list - that is, a constant time function that maps integers to the nth coordinate?

Answer 1

your listing should come from the upper right corner to the lower left, naturally.

maintain the border as a priority. start from the upper right corner, which is the only entry on the border.

at each step, pull the maximum element from PQ and paste its three descendants (West, South and Southwest) into the queue without creating duplicates _{(maybe use the actual array of arrays to return to the queue, but that means extra space ... well , there are no more than n these short (say, vertical) arrays, each of which is no more than a few elements, and they never grow / do not move up, but only down).}

The queue length is O (n) - think "diagonals", even if curved , -

and you create results n ² so the overall complexity depends on the efficiency of the queue implementation. If it is a logarithmic value, it will be O (n ² log n) and if it is linear (using a hash table, since we know the range of values), O (n ² ) as a whole; but it will be online , - O (1) ... O (log n) for the received pair.

If accuracy allows (for your range, it looks like it), pre-compute the logarithms of your coordinates and arrange the pairs by log(x) + log(y) instead of x * y , trading O (n ² ) for n logarithms and complements O (n ² ).

edit: see this one for actual Haskell code for another, very similar algorithm; it also contains an additional hint on how to speed it up using another coefficient 2 ( xy==yx ), so work only with the triangular half of the square - this will also halve the required space. And it looks like there is 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 how quickly you would like a generation and how quickly you could change the borders of a square.

This problem is akin to generating different numbers in the multiplication table (whose power was studied by Paul Erdos and the fastest known algorithm for calculating exactly O (n ^ 2)).

One way to look at generating sections of your list (assuming you don't list billions of coordinates) is to quickly hash a partial set of i*j in descending and sorting order. To make the hash accurate, we extend it below the selected range [n, k] until n * l falls below k*k for some l . For example, for the coordinate range from (10.10) to (7.7), we expand our hash to (5.5), so that (10.5), which is larger 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 ba}); 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) 

Answer 3

I have not tested this idea. You can quickly generate a list of all coordinates in approximately the correct order, simply by removing the diagonals from lower right to upper left, as with the argument for counting rationality . This will give you a combo box.

There are sorting methods that can take advantage of this to give you a faster look. See What sorting algorithm is best for re-sorting an almost completely sorted list? for discussion. You can always try different sorting algorithms to see what works best for your data.