Ordered Cartesian Coordinates

April 21, 2015

I’ve seen this discussed on several interview-question web forums, and people always claim to be able to do better than O(n2), but they are invariably wrong; there are O(n2) elements in the solution, so it isn’t possible to enumerate them in time less than O(n2). Thus, the interviewer’s challenge to find a better time than O(n2) is impossible (and a little bit mean, unless the candidate is confident of his answer, which might be the reason the interviewer asks the question). Here’s our solution:

(define (lt? x y)
  (or (< (car x) (car y))
      (and (= (car x) (car y))
           (v (cadr x) (cadr y)))))

(define (pairs n)
  (map cdr (sort lt?
    (list-of (list (* a b) a b)
      (a range 1 (+ n 1))
      (b range 1 (+ n 1))))))

The list comprehension forms triples of product, first coordinate, and second coordinate, the sort arranges them by ascending product and by ascending first coordinate in case of ties, and the map discards the product. Here’s an example:

> (pairs 0)
()
> (pairs 1)
((1 1))
> (pairs 2)
((1 1) (1 2) (2 1) (2 2))
> (pairs 3)
((1 1) (1 2) (2 1) (1 3) (3 1) (2 2) (2 3) (3 2) (3 3))

Our solution is short and simple. It’s amusing to read some of the other solutions. One common solution uses a hash table to collect pairs with like products, sorts the products, and outputs the pairs; that solution is potentially better than ours, since the sort is over the products instead of the pairs, but I doubt it will be faster in practice. Another solution uses a priority queue onto which pairs are pushed, then extracted in sorted order. Some people suggest a recursive solution that starts with a unit square, then increases the size of the square in steps, but that always falters; in our example, after you have (1,1) for the unit square and (1,1), (1,2), (2,1), (2,2) for the second square, you somehow have to insert (1,3) and (3,1) within the outgoing seqence when you move to the third square. Some people try to read along the diagonals of the times table, so they get (1,1), then (1,2), (2,1), then (1,3), (2,2), (3,1), and so on, but then they have to patch up the sort. It’s amazing how complicated some of the solutions turn out to be; I saw one 117-line Java solution that I never bothered to read.

We used list comprehensions from the Standard Prelude. You can run the program at http://ideone.com/lM3rIs.

Pages: 1 2

16 Responses to “Ordered Cartesian Coordinates”

  1. Rutger said

    No, we cannot find a solution better than O(n^2).
    This is because the result contains n^2 coordinates and we can produces each coordinate in O(1).

    But using a Python generator we can produce them on demand, minimizing memory to O(1).

    
    
    def coordinates(n):
    	for i in range(n):
    		for j in range(n):
    			yield (i,j)
    
    for c in coordinates(3):
    	print c 
    
  2. Rutger said

    Mm forgot the sorting constraint. In this case we need the entire list in memory anyways.. Sorting is O(n log n) << O(n^2).

    def coordinates(n):
    for i in range(n):
    for j in range(n):
    yield (i+1,j+1)

    l = sorted( [c for c in coordinates(3)], key=lambda x: x[0]*x[1] )
    print l

  3. Jaime said

    Sorting is actually O(n^2 log n^2), which is worse than O(n^2).

  4. Rutger said

    Mm true. What about the solution built by mr. Programming Praxis?
    He uses a sort function (https://programmingpraxis.com/contents/standard-prelude/#sorting) as well (O(n log n), with n=#coordinates)

  5. programmingpraxis said

    I didn’t do it, but instead of a comparison-based sort at O(n log n) you could do a radix sort or some other O(n) sort. That would truly reduce the overall time to O(n2).

  6. Jussi Piitulainen said

    This Python, I believe, generates the sequence in O(n) space. There are n generator objects, one for each row of the multiplication table, which the heapq.merge combines to yield each (rk, (r, k)) in increasing order. The sequence is then pulled to memory at once for printing. That’s not merge’s fault.

    from heapq import merge
    def row(r, n): return ((r * k, (r, k)) for k in	range(1, n + 1))
    n = 3
    print([p for w, p in merge(*(row(r, n) for r in range(1, n + 1)))])
    
  7. Will_Ness said

    The enumeration in descending order:

    enuNM n = foldi (\(x:xs) ys-> x : merge xs ys) [] $
        [ (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<-[n,n-1..1]]
    
    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
    

    Reversing the sequence involves some straightforward changes in the code.

  8. Will_Ness said

    Forgot to add, the code’s in Haskell; it runs empirically at ~ n^1.08 producing first n=100,000 entries for a similar, slightly different problem (seen here ) at ranges on the order of 10^8.

  9. Destabilizer said

    I wrote this solution (on Python):

    def coords(n):
    for i in range(n*n):
    yield(i//n+1, i%n+1)

    So, I think it works for O(n).
    In action:

    >>> list(coords(4))
    [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)]

  10. Destabilizer said

    Codepad source:
    http://codepad.org/68GCPgmN

  11. Jussi Piitulainen said

    @Destabilizer, the task was to yield the pairs “ordered by their product”, so (2, 1), for example, should come before (1, 3). It may or may not come before (1, 2), which has the same product. You’ve produced a “row-major” order, or it might be called a “lexicographic order”. (Nice expression of it, though.)

    It’s also not O(n) time. Your yield statement is executed n² times which is more than O(n). Do see Praxis’s discussion or first comment above.

  12. Rajeev. P said

    class Program
    {
    static void Main(string[] args)
    {
    int n = 4;
    Hashtable ht = new Hashtable();
    int count =0;
    for (int i = 1; i <= n; i++)
    {
    for (int j = 1; j 1)
    {
    if (!ht.ContainsValue(string.Format(“({0},{1})”, j, i)))
    {
    count++;
    ht.Add(count, string.Format(“({0},{1})”, j, i));
    }
    }
    }
    }
    }

    foreach (int key in ht.Keys.Cast().OrderBy(x=>x))
    {
    Console.WriteLine(ht[key]);
    }

    Console.ReadKey();
    }
    }

  13. Rajeev. P said

    Sorry HTML Truncated

    class Program
    {
    static void Main(string[] args)
    {
    int n = 4;
    Hashtable ht = new Hashtable();
    int count =0;
    for (int i = 1; i <= n; i++)
    {
    for (int j = 1; j <= n; j++)
    {
    if (!ht.ContainsValue(string.Format("({0},{1})", i, j)))
    {
    count++;
    ht.Add(count, string.Format("({0},{1})", i, j));
    if (j > 1)
    {
    if (!ht.ContainsValue(string.Format("({0},{1})", j, i)))
    {
    count++;
    ht.Add(count, string.Format("({0},{1})", j, i));
    }
    }
    }
    }
    }

    foreach (int key in ht.Keys.Cast<int>().OrderBy(x=>x))
    {
    Console.WriteLine(ht[key]);
    }

    Console.ReadKey();
    }
    }

  14. fisherro said

    My first attempt, which I believe is correct.

    #include <vector>
    #include <utility>
    #include <iostream>
    
    typedef std::vector<std::pair<int, int>> Coords;
    
    void ugly_sort(Coords& v)
    {
        using namespace std::placeholders;
        std::sort(v.begin(), v.end(),
            std::bind(std::less<int>(),
                std::bind(std::multiplies<int>(),
                    std::bind(&Coords::value_type::first, _1),
                    std::bind(&Coords::value_type::second, _1)),
                std::bind(std::multiplies<int>(),
                    std::bind(&Coords::value_type::first, _2),
                    std::bind(&Coords::value_type::second, _2))));
    }
    
    void lambda_sort(Coords& v)
    {
        std::sort(v.begin(), v.end(),
            [](const Coords::value_type& a, const Coords::value_type& b)
            { return (a.first * a.second) < (b.first * b.second); });
    }
    
    Coords generate(int n)
    {
        Coords v;
        for (int x = 1; x <= n; ++x) {
            for (int y = 1; y <= n; ++y) {
                v.push_back(std::make_pair(x, y));
            }
        }
    #if 0
        ugly_sort(v);
    #else
        lambda_sort(v);
    #endif
        return v;
    }
    
    int main(int argc, char** argv)
    {
        auto v = generate(3);
        for (const auto& p: v) {
            std::cout << "(" << p.first << ", " << p.second << "): " <<
                (p.first * p.second) << "\n";
        }
    }
    
  15. fisherro said

    I made a second attempt, but this one fails for n ≥ 5.

    #include <vector>
    #include <utility>
    #include <iostream>
    
    //This one fails an n = 5.
    std::vector<std::pair<int, int>> generate(int n)
    {
        std::vector<std::pair<int, int>> v;
        for (int x = 1; x <= n; ++x) {
            for (int y = x; y <= n; ++y) {
                v.push_back(std::make_pair(x, y));
                if (x != y) v.push_back(std::make_pair(y, x));
            }
        }
        return v;
    }
    
    int main(int argc, char** argv)
    {
        auto v = generate(5);
        for (const auto& p: v) {
            std::cout << "(" << p.first << ", " << p.second << "): " <<
                (p.first * p.second) << "\n";
        }
    }
    
  16. cristi said

    how about:

    int i = 0;

    for (i=1; i<N; i++)
    {
    printf("(%d,%d) ",i,i);
    printf("(%d,%d) ",i,i+1);
    printf("(%d,%d) ",i+1,i);
    if ( i+2 <= N )
    {
    printf("(%d,%d) ",i,i+2);
    printf("(%d,%d)",i+2,i);
    }
    printf("\n");
    }
    printf("(%d,%d)\n",N,N);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: