问题：
给定数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 之前一直迭代到100 i 减少了。
我正在寻找一种迭代的方法，使得产生的值按降序排列，因为这样我只需通过调用就可以得到答案 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()
问题中的循环模式就像
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）。
您可以像这样生成集合：
>>> 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
但找到整个列表的速度较慢。
给定数n，是否有一种有效的算法来从集合{1 ... n}中获得2组合的列表，并按组合乘积的值排序？
不太清楚你在追求什么，但这是一种在python中编码的简单方法：
n = SOME_INTEGER
from itertools import combinations
sorted(combinations(set(xrange(1,n+1)),2),key=lambda x: x[0]*x[1])
或者，最大的产品优先：
sorted(combinations(set(xrange(1,n+1)),2),key=lambda x: x[0]*x[1],reverse=True)
你知道当a> c时，（a，b）总是会出现在（a，c）之前。所以你可以保留每个类[（a，b），（a，b-1），（a，b-2），...]的一个代表，并在这些中进行选择。使用堆。此实现需要O（n ^ 2 * log（n））时间和O（n）空间：
import heapq
def combinations_prod_desc(n):
h = [(-i*i, i, i) for i in xrange(1, n+1)]
h.reverse()
while len(h) > 0:
u = h[0]
yield u
b = u[2]
if b <= 1:
heapq.heappop(h)
continue
a = u[1]
b -= 1
heapq.heappushpop(h, (-a*b, a, b))
return
从Python 2.6开始，heapq模块内置了合并算法。利用这一点，我们可以获得相同算法的单行实现：
def combinations_prod_desc_compact(n):
return heapq.merge(*[(lambda a : ((-a*b, a, b) for b in xrange(a, 0, -1)))(a) for a in xrange(1, n+1)])
由于Python理解的语义奇怪，上面的以下天真版本不起作用。如果有人对探索Python的语言规范感兴趣，那么查找以下代码未给出我们想要的结果的确切原因将会很有趣，即使它看起来像“应该”：
def combinations_prod_desc_nonworking(n):
return heapq.merge(*[((-a*b, a, b) for b in xrange(a, 0, -1)) for a in xrange(1, n+1)])