问题:
给定一个数字 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 语言的良好答案的资格,我可以尝试使用任何语言,只要您对其进行解释,以便我(或其他任何人)能够充分理解它。
最佳答案
你可以使用堆/优先级 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()
关于python - 乘法组合算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15537479/