Multiplicative combination algorithm

Question

Problem:

Given a number n, is there an efficient algorithm to obtain a list of 2-combinations from the set {1...n}, sorted by the value of the product of the combination?

I need this in order to determine the largest product of two *-digit numbers that satisfies a certain condition. If the list is unsorted, I must first determine all combinations that satisfy the condition, then iterate through those to find the combination with the largest product, which is inefficient.

As an example, given n = 3, the combinations possible are:

Combination:      Product:
   3, 3              9
   3, 2              6
   3, 1              3
   2, 2              4
   2, 1              2
   1, 1              1

Sorted by the value of the product in descending order, this is:

Combination:      Product:
   3, 3              9
   2, 3              6
   2, 2              4
   1, 3              3
   1, 2              2
   1, 1              1

Extra background:

I just solved a Project Euler question regarding finding the largest palindromic number that is a product of two 3 digit numbers. My approach was to iterate downward from 999 (the largest 3 digit number) with two factors and find the product of each combination, additionally checking whether the number was palindromic:

def maxpal():
    for i in reversed(range(100,1000)):

        # Since we only want unique combinations, we only
        # need to iterate up to i

        for j in reversed(range(100,i)):   
            if str(i*j) == str(i*j)[::-1]:
                yield i*j

print max(maxpal())

Note that the first list in the example iterates over factors in exactly the same order as this code. My initial assumption was that since I was iterating downwards, the first palindrome I found would be the largest one. This is clearly not the case, since j iterates all the way to 100 before i is decremented.

I am looking for a way to iterate such that the values are yielded are in descending order, since this allows me to get the answer simply by invoking next(maxpal) once, which is much more efficient.

EDIT:

In the interests of not disqualifying a good answer in a language that isn't Python, I'm OK with an attempt in any language as long as you explain it so that I (or anyone else) can sufficiently understand it.

Answer 1

You can use a heap/priority Q.

Start with (n,n), insert in the heap. Your comparison function = compare the products.

Whenever you extract (x,y), you insert (x-1,y) and (x,y-1) if needed (you can maintain a hashtable to check for dupes if you want).

Here is some quick (and ugly looking) code to demonstrate the above. Note that this is a lazy iterator, allowing us to do a next and stopping as soon as your condition is satisfied. (Note: Using larsman's suggestion (comment below) will make it better, but the idea is similar)

import heapq

def mult_comb(n):
    heap = []
    visited = {}
    visited[n*n] = True
    prod = n*n
    heapq.heappush(heap, (-prod, n, n))
    while prod > 1:
        (prod,x,y) = heapq.heappop(heap)
        yield -prod,x,y
        prod = -prod

        prod1 = (x-1)*y
        prod2 = x*(y-1)
        if not prod1 in visited:
            heapq.heappush(heap, (-prod1, x-1,y))
            visited[prod1] = True
        if not prod2 in visited:
            heapq.heappush(heap, (-prod2, x,y-1))
            visited[prod2] = True

def main():
    for tup in mult_comb(10):
        print tup

if __name__ == "__main__":
    main()

Answer 2

The loop schema in the question is like

for i in reversed(range(100,1000)):
    for j in reversed(range(100,i)):   
        if str(i*j) is palindromic, yield i*j

and the requested solution is to find a way to deliver in descending order the same numbers as that loop tests. The code above generates 404550 i,j pairs; 1231 of those pairs are palindromic; 2180 of the pairs are larger than the ultimate result 906609 = 913*993.

The methods suggested so far may generate all or many of the possible pairs; and those that generate only a few of the possible pairs still test many more number pairs than necessary.

The following code, by contrast, tests only 572 pairs, of which 3 are palindromes. It depends mainly on two observations: first, any six-digit palindrome is a multiple of 11 because any number with digit form abccba is equal to a*100001 + b*10010 + c*1100, and all three of 100001, 10010, and 1100 are multiples of 11. Second, if our best find so far has value k and we are testing a given value of i with i≤j then there is no need to test any j < k/i or any j<i.

def pal():
    nTop = 1000;    best, jin, jpal = 0, 0, 0
    # Test pairs (i, j) with i <= j
    for i in range(nTop, nTop//10-1, -1):
        jDel = 11 if i%11 else 1
        jHi = (nTop//jDel)*jDel
        jLo = max(i, best//i) - 1;
        for j in range(jHi, jLo, -jDel):
            jin += 1
            if str(i*j)==str(i*j)[::-1] :
                jpal += 1
                best = max(best, i*j)
    return (best, jin, jpal)

With the above code, pal() returns the tuple (906609, 572, 3).

Answer 3

You can generate the set like so:

>>> n=3
>>> s={(min(x,y),max(x,y)) for x in range(1,n+1) for y in range(1,n+1)}
>>> s
set([(1, 2), (1, 3), (3, 3), (2, 3), (2, 2), (1, 1)])

And sort it like this:

>>> sorted(s,key=lambda t: -t[0]*t[1])
[(3, 3), (2, 3), (2, 2), (1, 3), (1, 2), (1, 1)]

But you don't need to do it this way at all. Just use a nested comprehension:

>>> [(x,y) for x in range(3,0,-1) for y in range(3,x-1,-1)]
[(3, 3), (2, 3), (2, 2), (1, 3), (1, 2), (1, 1)]

Which leads to a one liner for that paticular problem:

print max(x*y for x in range(1000,100,-1) for y in range(1000,x-1,-1) 
          if str(x*y)==str(x*y)[::-1])

If you really want to do it the way you propose, you can use bisect:

def PE4():
    import bisect

    def ispal(n):
        return str(n)==str(n)[::-1]

    r=[]
    for x in xrange(1000,100,-1):
        for y in xrange(1000,x-1,-1):
            if ispal(x*y): bisect.insort(r,(x*y,x,y))

    return r[-1]

The list r ends up in increasing order since that is the only order supported by bisect.

You can also use heapq:

def PE4_4():
    import heapq

    def ispal(n): return str(n)==str(n)[::-1]

    r=[]
    for x in xrange(100,1001):
        for y in xrange(x,1001):
            if ispal(x*y): heapq.heappush(r,(-x*y,x,y))     

    return (-r[0][0],r[0][1],r[0][2])   

If I time these:

import timeit

def PE4_1():
    def ispal(n): return str(n)==str(n)[::-1]
    return max((x*y,x,y) for x in xrange(1000,99,-1) for y in xrange(1000,x-1,-1) if ispal(x*y))

def PE4_2():
    import bisect
    def ispal(n): return str(n)==str(n)[::-1]
    r=[]
    for x in xrange(1000,99,-1):
        for y in xrange(1000,x-1,-1):
            if ispal(x*y): bisect.insort(r,(x*y,x,y))

    return r[-1]

def PE4_3():
    import bisect
    def ispal(n): return str(n)==str(n)[::-1]
    r=[]
    for x in xrange(100,1001):
        for y in xrange(x,1001):
            if ispal(x*y): bisect.insort(r,(x*y,x,y))

    return r[-1]

def PE4_4():
    import heapq
    def ispal(n): return str(n)==str(n)[::-1]
    r=[]
    for x in xrange(100,1001):
        for y in xrange(x,1001):
            if ispal(x*y): heapq.heappush(r,(-x*y,x,y))     

    return (-r[0][0],r[0][1],r[0][2])         

n=25
for f in (PE4_1,PE4_2,PE4_3,PE4_4):
    fn=f.__name__
    print fn+':'
    print '\t',f()
    res=str(timeit.timeit('{}()'.format(fn),setup="from __main__ import {}".format(fn), number=n))
    print '\t'+res+' seconds\n'

It prints:

PE4_1:
    (906609, 913, 993)
    10.9998581409 seconds

PE4_2:
    (906609, 913, 993)
    10.5356709957 seconds

PE4_3:
    (906609, 913, 993)
    10.9682159424 seconds

PE4_4:
    (906609, 913, 993)
    11.3141870499 seconds

Shows that the bisect method is marginally faster, followed by the max of a generator. heapq is the slowest method (marginally)

Long answer, but probably the best way to produce the order of list you want is to sort it that way:

---

I timed Knooth's solution and it is massively superior to find the first number with a constraint:

def PE4_6():
    def ispal(n): return str(n)==str(n)[::-1]
    def gen(n=1000):
        heap=[]
        visited=set([n*n])
        prod=n*n
        heapq.heappush(heap,(-prod,n,n))
        while abs(prod)>1:
            (prod,x,y)=heapq.heappop(heap)
            yield -prod,x,y
            p1,p2=(x-1)*y, x*(y-1)
            if p1 not in visited:
                heapq.heappush(heap, (-p1, x-1,y))
                visited.add(p1)
            if p2 not in visited:
                heapq.heappush(heap, (-p2, x,y-1))
                visited.add(p2)

    it=iter(gen())
    t=next(it)
    while not ispal(t[0]):
        t=next(it)

    return t   

But slower to find the whole list.