乘法组合算法

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

额外背景:

我刚刚解决了关于找到最大回文数的项目欧拉问题,该数字是两个3位数字的乘积.我的方法是用两个因子从999(最大的3位数字)向下迭代,找到每个组合的乘积,另外检查数字是否是回文:

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在i递减之前一直迭代到100 .

我正在寻找一种迭代的方法,使得产生的值按降序排列,因为这允许我简单地通过调用next(maxpal)一次得到答案,这样效率更高.

编辑:

为了不用非Python语言取消一个好答案的资格,只要你解释它,我就可以试用任何语言,这样我(或其他任何人)就可以充分理解它.

Answer 1

您可以使用堆/优先级Q.

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