11

问题：

给定一个数字 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

额外背景：

我刚刚解决了一个 Project Euler 问题，该问题是关于找到两个 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 语言的好答案的资格，我可以尝试使用任何语言，只要您解释它以便我（或其他任何人）能够充分理解它。

4

5 回答 5

8

您可以使用堆/优先级 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()
于 2013-03-21T01:12:19.107 回答
3

问题中的循环模式就像

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然后不需要测试 anyj < k/i或 any 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)。

于 2013-03-21T05:32:28.157 回答
1

您可以像这样生成集合：

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

但是找到整个列表的速度较慢。

于 2013-03-21T01:35:07.390 回答
0

给定一个数字 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)
于 2013-03-21T00:58:18.933 回答
0

你知道当 b > 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)])
于 2013-03-21T01:37:38.737 回答