python - 乘法组合算法

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

按产品值(value)降序排列，这是:

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