Algorithm for generating an ordered list of pair products

Question

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

My attempt is (in haskell):

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

Answer 1

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 ≤ x ≤ y ≤ 99 but I'm printing y first to match your lists.