问题 乘法组合算法


问题:

给定数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语言取消一个好答案的资格,只要你解释它以便我(或任何其他人)能够充分理解它,我就可以尝试任何语言。


8399
2018-03-21 00:43


起源

具体是哪个问题? - John
@johnthexiii Q4我想。这是几天前,但我只有11岁,所以就在那之前。 - Asad Saeeduddin
如果这是Q4,那么有一个更容易的方法。两个k位数的乘积正好有2×k个数字。你只需要生成2×k位数的回文(并对它们进行一些过滤)。回文数量非常少,如果您使用回文的区别特征,则很容易确定。 - Fred Foo
@larsmans这是我采取的第一种方法。我按降序生成了所有可能的回文,但随后意识到找到n位因子是非常昂贵的(首先找到素数因子,然后找到给出n位因子的乘法组合)。魔鬼在 (and do some filtering on them) - Asad Saeeduddin
@Asad现在转换成Python已经太晚了,那么Haskell实现是否可以接受? - Daniel Fischer


答案:


您可以使用堆/优先级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()

8
2018-03-21 01:12



由于OP需要双元素子集,因此最好插入(x-1,y)和(x-1,y-1)以在早期强制执行约束x <= y。 - Fred Foo
@larsmans:我误读了你的评论(并删除了我之前的评论,如果这让你感到困惑:-))。你可能是对的。 - Knoothe
heapq 将始终在其根目录中具有堆中的最小值。但是,最后一个值根本不保证是最大值。您仍然需要对其进行排序以获得最大值。 - dawg
@Drewk:将其视为2D矩阵M [n,n],其中M [i,j] = i * j。这具有Young的Tableau属性:每个行和列都已排序。现在,您希望按排序顺序遍历此矩阵。一种方法是在最大堆中插入并按照上面的描述进行提取/插入。我不明白你的反对意见。我正在回答主要问题,而不是背景项目欧拉问题。 - Knoothe
好吧,当我发表评论时你没有代码,所以这是一个实现评论。你的代码很棒。 +1 - dawg


问题中的循环模式就像

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


3
2018-03-21 05:32



这实际上是这里一英里最快的! - dawg
+1:但这是解决项目欧拉问题(在背景下提交:-)),而不是实际问的问题(这本身就是一个有趣的问题)。 - Knoothe


您可以像这样生成集合:

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

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


1
2018-03-21 01:35



但这实际上会生成所有值以便找到最大值,因为它不会按降序生成它们。 (当然,对于这么大的数字,这在现代硬件上不是问题。但它不能扩展。) - rici
这更接近,因为它在4次迭代中找到了所需的回文,但它仍然没有输出按产品大小排序的列表。例如,上一个代码段中生成器的前几个输出是: [888888, 861168, 886688, 906609, 824428, 819918, 828828, 855558, 840048, 853358]。它也不严格输出组合,因为某些产品会多次出现在列表中(因为第二个因子从1000减少到x而不是从x减少到100)。仍然是+1。 - Asad Saeeduddin
您使用堆的方式缺少需要迭代器的点。请参阅我的答案中的示例代码。例如,你只需要查看大约114,000个数字就可以达到第三大回文,而在你的实现中,你会看到大约一百万,然后将回文插入堆中。注意将它与我的实现进行比较? - Knoothe


给定数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)

0
2018-03-21 00:58



这里的问题是你首先生成一个未排序的组合列表, 然后 整理它们。我们的想法是生成一个排序列表。 - Asad Saeeduddin
啊,现在我明白你所追求的......至少是紧凑的优点,如果效率不高;) - isedev


你知道当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)])

0
2018-03-21 01:37