乘法组合算法

Question

问题：

给定一个数字 n，是否有一种高效的方法可以从集合 {1...n} 中获取 2 个数字的组合，并按照组合的乘积值进行排序？

我需要这个列表是为了找出满足某种条件的两个 * 位数的最大乘积。如果列表没有排序，我必须先找出所有满足条件的组合，然后再逐个检查，找出乘积最大的组合，这样效率就很低了。

举个例子，假设 n = 3，可能的组合有：

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

按照乘积值从大到小排序，结果是：

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

额外背景：

我刚刚解决了一个 Project Euler 的问题，内容是找出两个三位数相乘得到的最大回文数。我采用的方法是从 999（最大的三位数）开始向下遍历，使用两个因子，计算每个组合的乘积，同时检查这个数字是否是回文数：

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())

注意，示例中的第一个列表与这段代码的因子遍历顺序是完全一致的。我最开始的假设是，由于我是在向下遍历，所以我找到的第一个回文数就是最大的。然而，事实并非如此，因为 j 会一直遍历到 100，才会让 i 减小。

我希望找到一种遍历方式，使得得到的值是按降序排列的，这样我只需调用一次 next(maxpal) 就能得到答案，这样效率会高很多。

编辑：

为了不排除用其他语言给出的好答案，只要你能解释清楚，让我（或其他人）能理解，我都可以接受任何语言的尝试。

Answer 1

你可以这样生成一个集合：

>>> 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)])

然后可以这样对它进行排序：

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

不过其实你完全不需要这样做。只需使用嵌套的理解方式：

>>> [(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)]

这样就能用一行代码解决这个特定的问题：

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])

如果你真的想按照你提议的方式来做，可以使用 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]

列表 r 最终会按升序排列，因为 bisect 只支持这种排序方式。

你也可以使用 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])   

如果我对这些进行计时：

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'

它会输出：

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

结果显示 bisect 方法稍微快一点，其次是生成器的最大值。 heapq 是最慢的方法（也只是稍微慢一点）。

虽然回答有点长，但可能得到你想要的列表顺序的最好方法就是这样排序：

---

我对 Knooth 的解决方案进行了计时，发现它在有约束条件的情况下找到第一个数字的效率非常高：

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   

但在找到整个列表时就慢一些。

Answer 2

问题中的循环结构大致是这样的：

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

而我们想要的解决方案是找到一种方法，以降序排列与这个循环测试的数字相同。上面的代码生成了404550对i,j的组合；其中1231对是回文数；2180对的值都大于最终结果906609 = 913*993。

到目前为止，建议的方法可能会生成所有或许多可能的组合；而那些只生成少量组合的方法，仍然会测试比必要的更多的数字组合。

相比之下，以下代码只测试了572对组合，其中有3对是回文数。这个方法主要依赖于两个观察点：首先，任何六位数的回文数都是11的倍数，因为任何形式为abccba的数字可以表示为a*100001 + b*10010 + c*1100，而100001、10010和1100这三个数都是11的倍数。其次，如果我们目前找到的最佳值是k，并且我们正在测试一个给定的i值，且满足i≤j，那么就没有必要测试任何j < k/i或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)

使用上面的代码，pal()返回的结果是元组(906609, 572, 3)。

Answer 3

你可以使用堆或者优先队列。

首先从(n,n)开始，把它放进堆里。你的比较方法就是比较这些数的乘积。

每当你取出(x,y)的时候，如果需要的话，就插入(x-1,y)和(x,y-1)（如果你想的话，可以用一个哈希表来检查重复的值）。

下面是一些快速（看起来有点丑）的代码来演示上面的内容。注意，这个是一个懒惰的迭代器，允许我们执行下一步，并在满足条件时立即停止。（注意：使用larsman的建议（下面的评论）会让它更好，但思路是类似的）

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()