Перестановки Python itertools работают очень медленно

Question

Работает в SuSE Linux,

Это быстрый и грязный скрипт для решения головоломки геокэшинга (GC9K63A).
Первая попытка сделать что-нибудь на питоне. Я добавил печать "." чтобы дать доказательство жизни, но точка не появляется. Раньше бегал неделю безрезультатно.

         items = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ,14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]
    from itertools import permutations
    for perm in permutations(items):
    
     A=perm[0]
     B=perm[1]
     C=perm[2]
     D=perm[3]
     E=perm[4]
     F=perm[5]
     G=perm[6]
     H=perm[7]
     I=perm[8]
     J=perm[9]
     K=perm[10]
     L=perm[11]
     M=perm[12]
     N=perm[13]
     O=perm[14]
     P=perm[15]
     Q=perm[16]
     R=perm[17]
     S=perm[18]
     T=perm[19]
     U=perm[20]
     V=perm[21]
     W=perm[22]
     X=perm[23]
     Y=perm[24]
     Z=perm[25]
    
    
     if     (A - B - C - D - E - F + G + H + I - J - K + L - M + N - O + P + Q + R + S - T - U - V - W - X - Y + Z) == -55 and (A - B - C - D + E - F + G - H + I - J - K - L - M + N - O + P - Q + R - S - T - U + V + W + X - Y + Z) == -37 and (A + B + C - D + E - F + G - H + I + J - K + L + M - N - O + P - Q - R + S - T + U - V - W + X - Y - Z) == -27 and (A + B - C - D - E + F + G - H + I + J + K + L + M + N - O - P + Q + R - S - T - U - V + W - X - Y + Z) == 13 and (A + B - C + D - E + F + G + H - I + J + K + L - M + N + O - P + Q - R - S - T - U - V - W - X - Y + Z) == -59 and (A - B - C + D - E - F + G - H + I - J - K + L - M + N + O + P - Q + R - S - T - U + V + W - X - Y + Z) == 7 and (A - B - C - D - E + F + G - H + I - J - K + L + M - N + O - P + Q + R - S + T + U + V - W - X + Y + Z) == 91 and (A - B + C + D - E + F + G + H + I - J + K - L + M - N - O - P - Q + R + S - T - U + V + W + X - Y - Z) == 19 and (A + B + C - D + E + F - G - H - I + J - K + L - M + N - O + P - Q + R + S - T - U + V + W - X - Y - Z) == -51 and (A - B - C + D - E - F - G + H + I + J + K + L + M + N - O + P - Q + R + S + T - U + V + W + X - Y - Z) == 79 and (A - B + C + D - E - F - G - H - I - J - K - L + M - N + O + P - Q + R - S - T + U + V + W + X + Y - Z) == 29 and (A + B - C - D - E - F + G + H + I - J + K - L + M + N + O + P + Q - R - S - T + U - V - W - X - Y + Z) == -5 and (A + B - C + D + E - F + G + H - I - J + K + L + M + N - O - P - Q + R - S + T - U + V - W + X - Y - Z) == -5 and (A + B - C - D - E + F - G + H - I - J - K - L - M + N - O + P + Q + R + S + T + U - V - W + X - Y + Z) == 55 and (A - B + C + D + E + F + G + H - I - J + K - L + M - N - O + P + Q - R + S - T - U + V + W + X - Y + Z) == 1 and (A - B + C - D - E - F - G - H - I + J + K - L + M - N - O - P + Q + R + S - T + U + V - W + X - Y - Z) == -57 and (A + B - C - D - E - F - G + H - I - J - K - L - M + N - O - P + Q + R - S - T - U - V - W + X - Y + Z) == -117 and (A + B - C + D + E - F - G - H - I + J + K - L + M + N - O - P + Q + R - S - T + U + V - W + X + Y + Z) == 51 and (A - B + C - D - E - F - G + H - I + J - K + L - M - N + O + P + Q - R - S + T + U - V - W + X + Y + Z) == 3 
    
    
    
         print  A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z
    
    else:
         print "."

Answer 1

Здесь следует отметить несколько деталей.

Во-первых, вы сказали, что позволили этому коду работать неделю безрезультатно.
Обратите внимание, что даже если результат будет найден, он не остановится. Так что, если вы не просмотрели весь вывод, есть большая вероятность, что результат действительно был, но его смыли точки, следующие за ним.
Добавить такое условие было бы так же просто, как включить breakзаявление после того, как вы напечатали свой результат.

Затем в операторах сразу после начала цикла for вы шаг за шагом присваиваете новые значения различным переменным, названным буквами. Это можно сделать с помощью распаковки внутри цикла for. Это должно привести к небольшому ускорению, а также сделать код более читабельным.

Наконец, операция ввода-вывода печати может значительно замедлить работу вашего кода.
Чтобы быть уверенным в этом, я попробовал это:
я добавил счетчик в начале и добавил этот счетчик в оператор печати.
Таким образом, я мог видеть, сколько перестановок может обрабатывать сценарий в течение заданного периода времени.
Запуск около 10 секунд приводит к проверке около 100 000 перестановок.
Затем я добавил дополнительное условие if, которое проверяет, делится ли счетчик на 100000, и только потом печатает строку.
За те же 10 секунд эта версия скрипта проверяет 2500000 перестановок.

Модифицированный код, к которому я пришел в самом конце, выглядит так:

      counter = 0
items = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 ,14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]
from itertools import permutations
for A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z in permutations(items):
  if (A - B - C - D - E - F + G + H + I - J - K + L - M + N - O + P + Q + R + S - T - U - V - W - X - Y + Z) == -55 and (A - B - C - D + E - F + G - H + I - J - K - L - M + N - O + P - Q + R - S - T - U + V + W + X - Y + Z) == -37 and (A + B + C - D + E - F + G - H + I + J - K + L + M - N - O + P - Q - R + S - T + U - V - W + X - Y - Z) == -27 and (A + B - C - D - E + F + G - H + I + J + K + L + M + N - O - P + Q + R - S - T - U - V + W - X - Y + Z) == 13 and (A + B - C + D - E + F + G + H - I + J + K + L - M + N + O - P + Q - R - S - T - U - V - W - X - Y + Z) == -59 and (A - B - C + D - E - F + G - H + I - J - K + L - M + N + O + P - Q + R - S - T - U + V + W - X - Y + Z) == 7 and (A - B - C - D - E + F + G - H + I - J - K + L + M - N + O - P + Q + R - S + T + U + V - W - X + Y + Z) == 91 and (A - B + C + D - E + F + G + H + I - J + K - L + M - N - O - P - Q + R + S - T - U + V + W + X - Y - Z) == 19 and (A + B + C - D + E + F - G - H - I + J - K + L - M + N - O + P - Q + R + S - T - U + V + W - X - Y - Z) == -51 and (A - B - C + D - E - F - G + H + I + J + K + L + M + N - O + P - Q + R + S + T - U + V + W + X - Y - Z) == 79 and (A - B + C + D - E - F - G - H - I - J - K - L + M - N + O + P - Q + R - S - T + U + V + W + X + Y - Z) == 29 and (A + B - C - D - E - F + G + H + I - J + K - L + M + N + O + P + Q - R - S - T + U - V - W - X - Y + Z) == -5 and (A + B - C + D + E - F + G + H - I - J + K + L + M + N - O - P - Q + R - S + T - U + V - W + X - Y - Z) == -5 and (A + B - C - D - E + F - G + H - I - J - K - L - M + N - O + P + Q + R + S + T + U - V - W + X - Y + Z) == 55 and (A - B + C + D + E + F + G + H - I - J + K - L + M - N - O + P + Q - R + S - T - U + V + W + X - Y + Z) == 1 and (A - B + C - D - E - F - G - H - I + J + K - L + M - N - O - P + Q + R + S - T + U + V - W + X - Y - Z) == -57 and (A + B - C - D - E - F - G + H - I - J - K - L - M + N - O - P + Q + R - S - T - U - V - W + X - Y + Z) == -117 and (A + B - C + D + E - F - G - H - I + J + K - L + M + N - O - P + Q + R - S - T + U + V - W + X + Y + Z) == 51 and (A - B + C - D - E - F - G + H - I + J - K + L - M - N + O + P + Q - R - S + T + U - V - W + X + Y + Z) == 3 :
    print (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z)
    break
  else:
    counter += 1
    if counter % 100000 == 0:
      print (".", counter)

Также стоит иметь в виду, что количество перестановок, которые нужно проверить здесь, просто гигантское, поэтому даже с этими оптимизациями это, вероятно, все равно займет довольно много времени.
Чтобы быть точным, количество перестановок для проверки здесь равно !25 = 15511210043330985984000000, что, даже если бы вы смогли увеличить скорость проверки в миллион раз, все равно заняло бы около двух миллионов лет.
Если вам не нужно ждать несколько жизней, вам, вероятно, лучше поискать аналитическое решение.