次のようにセットを生成できます。
>>> 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]
bisect でサポートされている唯一の順序であるため、リストrは最終的に昇順になります。
次のものも使用できます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
ただし、リスト全体を見つけるのは遅くなります。