# Algorithm for generating an ordered list of pair products

For problem 4 in the euler project part of the assignment is to generate a list of products of 3-digit numbers.

The easy way is to just do a cartesian product (I think it's called), and after that find the largest value that is a palindrome.

My question is, is it possible to generate a list of pairs of which the product is ordered?

For example with 2-digits:

99,99
99,98
98,98
99,97
98,97
etc..


productsOf2Digits = productsOf2Digits' 99 99
productsOf2Digits' 90 90 = (90,90, 90*90) : []
productsOf2Digits' a b | a == b = (a,b,a*b) : productsOf2Digits' 99 (b-1)
| otherwise = (a,b,a*b) : productsOf2Digits' (a-1) b


Which yields:

(99,99,9801)
(99,98,9702)
(98,98,9604)
(99,97,9603)
(98,97,9506)
(97,97,9409)
(99,96,9504)
(98,96,9408)
(97,96,9312)
(96,96,9216)


The pair 99 96 breaks the ordering.

I think maybe I can exploit that the differences should be increasing?

Also, might it have to do with? http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/rationals.pdf

-
Just create all the products in natural order and then sort them. There are only about half a million of them, after all. Alternatively, create 1000 lists, each decreasing, and merge them in a balanced merge tree. (And it's "cartesian" with no h). – Henning Makholm Jul 10 '12 at 11:17
We have been asked not to discuss Project Euler problems. – Gerry Myerson Jul 10 '12 at 13:16
This is not really about the answer to the Euler problem, this is just an aspect of the solution that I find interesting, it's not at all necessary to order these pairs for the solution to the Euler problem. – Tinco Jul 10 '12 at 22:29
It might be worthwile to think of this on a log scale. I imagine a piece of log-log graph paper, with integer points corresponding to the line intersections. In that setup you want to enumerate crossings ordered by manhatten distance. Not sure how best to do that either, but it feels remotely related to scan conversion. – MvG Jul 12 '12 at 0:50

Here's a piece of C++ code for you.

#include <queue>
#include <iostream>

class Itm {
public:
int p, x, y;
Itm(int x, int y) : x(x), y(y), p(x*y) {}
Itm() : x(0), y(0), p(0) {}
bool operator<(const Itm& that) const {
return p < that.p || (p == that.p && x < that.x);
}
};

int main() {
std::priority_queue<Itm> q;
for (int i = 1; i < 100; ++i)
q.push(Itm(i, 99));
while (!q.empty()) {
Itm t = q.top();
std::cout << t.y << " * " << t.x << " = " << t.p << std::endl;
q.pop();
if (t.y > t.x)
q.push(Itm(t.x, t.y - 1));
}
}


The idea is to have a queue containing one item for each column (thing with same x value). Initially they all start of at the y=99 row. In each iteration, the maximal item is taken from the queue, and the item one below that added instead, unless doing so would leave the range of pairs we're interested in. In this case the range is 1 ≤ xy ≤ 99 but I'm printing y first to match your lists.

-