Мультипликативный комбинационный алгоритм
Проблема:
Учитывая число 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, я в порядке с попыткой на любом языке, пока вы объясняете это, чтобы я (или кто-либо еще) мог его в достаточной мере понять.
Ответы
Ответ 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)])
