Algorithm: iterate over 2 variables in order of descending product

Answer 1

C#

var A = new int[] {5, 7, 1, 3, 5, 12, 7, 10};
var B = new int[] {7, 2, 4, 1, 2, 7, 8};

(from a in A
 from b in B
 orderby a * b descending, a descending, b descending
 select new { a, b }).ToList().ForEach(i => Console.WriteLine("{0}x{1}={2}", i.a, i.b, i.a * i.b));

There, that's fairly elegant - just create a cartesian product of the two arrays sorting by first the product descending, then by the item in A, then finally by the item in B.

It handles singles and duplicates, it handles cross-join duplicates too - which you didn't ask for.

Which is roughly equivalent to:

var A = new int[] {5, 7, 1, 3, 5, 12, 7, 10};
var B = new int[] {7, 2, 4, 1, 2, 7, 8};

var C = from a in A
        from b in B
        orderby a * b descending
        select new { a, b };

foreach(var i in C)
{
    Console.WriteLine("{0}x{1}={2}", i.a, i.b, i.a * i.b);
}

Answer 2

You could maintain a priority queue that keeps, for each a, (the product with) the largest b that has not been used yet (with the product as the key it sorts by). Then each time, you pop the largest pair (a,b) from the heap, do whatever you want with it, and push (a,b-1) back. For example,

from heapq import heappush, heappop
heap = []
n = 5
for a in range(1,n+1): heappush(heap,(-a*n,a,n))
while heap:
    p,a,b = heappop(heap)
    print "%d = %d*%d" % (-p,a,b)
    if b>a:
        heappush(heap, (-a*(b-1),a,b-1))

prints exactly your output (except there's a 3 = 1 * 3 you missed :P). And you can change the if b>a to if b>0 if you want to keep duplicates. But note that this is O(n^2 log n), nothing can be better, and so you might as well put all the pairs into a list right at the start, sort by product, and iterate over elements of the list.

Answer 3

Fill a list with (a,b,product), sort by product then a, display the list.

Answer 4

in no particular language

for i in ( ( 5 * 5 ) .. 1 )
  for j in ( isqrt( i ) .. 1 )
    if ( i % j == 0 )
      print ( i / j ) + "*" + j + "=" + i

Answer 5

Edit: I see ShreevatsaR came up with the heap idea already, but I've got some more code, so here it stays.

You can totally brute force the PE question in seconds, but generalizing a bit, I can think of an approach.

Basically, you have a list of generators, one generator for each a. Each generator will generate the list of multiples of a.

Then you merge the generators together using a heap.

Here's my proof of concept in python 3. I had to use negative numbers to get it to sort descending.

import heapq

size = 3

def build_iter(i):
 return (-i*j for j in range(size, 0, -1))

iters = [build_iter(i) for i in range(1, size + 1)]

for val in heapq.merge(*iters):
 print(-val)

And the output:

9
6
6
4
3
3
2
2
1

Replace size with 1000 to get what you want.

Edit: This approach will find the highest palindrome for up to 100000*100000 problem space in a few seconds.

Answer 6

Ah. Here's a hint: there's an even better way. Takes a little number theory.

Answer 7

What you need to solve the problem you linked to is much simpler than the problem you posted here. To be fast enough you just have to write your loop like this:

# this is ruby
found = 0
999.downto(100) do |x|
  999.downto(x) do |y|
    break if x*y < found
    found = x*y if (x*y).palindrom?
  end
end

A solution for the complexer problem of printing the products in descending order is (in ruby):

# input: for simplicity all numbers need to be > 0
first = [1, 2, 3, 4, 5, 6]
second = [1, 2, 3, 4, 5]
# step 1: sort both list descending (! at end of method changes array)
first.sort!.reverse!
second.sort!.reverse!
# step 2: create array keeping pairs of indices still to be considered
pairs = Array.new(first.size) do |i|
          [i, 0] # [index in 1st array, index in 2nd array]
        end
# step 3: add 0 at the end of each array to simplify handling of
#         boundary conditions in step 4
first.push 0
second.push 0
# step 4: print out
loop do
  i, j = pairs.max do |a, b|
    first[a[0]]*second[a[1]] <=> first[b[0]]*second[b[1]]
  end
  product = first[i]*second[j]
  break if product.zero?
  puts "#{product} = #{first[i]} * #{second[j]}"
  pairs[i] = [i, j+1]
end

Repeated products are printed in order of descending first factor, but this could be changed for example by modifying the sorting criterion in the block given to max in step 4.

Calling the size of the first rsp. 2nd list m rsp. n, the running time of the algorithm is m^2*n. This can be sped up to log_2(m)*m*n by keeping the array "pairs" partially sorted as a heap (like in heap sort) so that each step in the loop takes log_2(m).

If negative numbers or zero are allowed as factors, one has to consider the cases >0, =0 and <0 for both factors separately, but these complications I prefer not to discuss...

If someone has questions about the implementation or the used ruby idioms, please feel free to ask.

Answer 8

To solve your problem faster, you don't really need complete ordering of the products, as long as you've got some readily computable bound on them. You're looking at the products A*B within a square in (A,B) space -- so start at the corner (maxAB,maxAB) and work your way down:

// c++ code

int findlargest(int maxval) {
  int best_product= -1;

  for(int A=maxval; A>=0; --A) {
    // note: no future products will be > A*maxval
    if(best_product > A*maxval) break;

    // no need to evaluate pairs below the diagonal!
    for(int B=maxval; B>=A; --B) {
      int AB= A*B;

      // note: products in inner loop are descending
      if(best_product > AB) break;
      if( we_want(AB) ) best_product= AB;
    }
  }

  return best_product;
}