Подтвердить что ты не робот

Мультипликативный комбинационный алгоритм

Проблема:

Учитывая число n, существует ли эффективный алгоритм для получения списка 2-комбинаций из набора {1... n}, отсортированного по значению произведения комбинации?

Мне нужно это, чтобы определить наибольшее произведение двух * -дицевых чисел, удовлетворяющих определенному условию. Если список несортирован, я должен сначала определить все комбинации, которые удовлетворяют условию, а затем перебрать их, чтобы найти комбинацию с самым большим продуктом, что неэффективно.

В качестве примера, учитывая 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

Дополнительный фон:

Я только что решил вопрос Эйлера Эйлера об обнаружении самого большого палиндромного числа, которое является произведением двух трехзначных чисел. Мой подход состоял в том, чтобы итератировать вниз от 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) один раз, что намного эффективнее.

EDIT:

В интересах того, чтобы не дисквалифицировать хороший ответ на языке, который не является Python, я в порядке с попыткой на любом языке, пока вы объясняете это, чтобы я (или кто-либо еще) мог его в достаточной мере понять.

4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете использовать кучу/приоритет 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()

Ответ 2

Схема цикла в вопросе похожа на

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

Вы можете сгенерировать набор следующим образом:

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

Это приводит к одному лайнеру для этой проблемы с paticular:

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

Но медленнее найти весь список.

Ответ 4

Учитывая число n, существует ли эффективный алгоритм для получения списка 2-комбинаций из набора {1... n}, отсортированного по значению произведения комбинации?

Не совсем уверен, что вам нужно, но это простой способ закодировать его в 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)

Ответ 5

Вы знаете, что (a, b) всегда будет раньше (a, c), когда b > 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)])