Python: суммирование по всем перестановкам

Question

Я застреваю, казалось бы, легкой проблемой, может кто-то помочь?

У меня есть два списка: a и b. Я могу назвать элементы списка a[i][j], где 0<i<100 и 0<j<100.

Я хочу найти все a[i][j] - b[k][l], где 0<i<100, 0<j<100, 0<k<100 и 0<l<100. А затем выполните суммирование по всем перестановкам из i, j, k, l.

Кто-нибудь знает элегантный простой способ этого?

Answer 1

import itertools 
sum(a[i][j] - b[k][l] for i, j, k, l in itertools.product(range(1, 100), repeat=4)) 

itertools.product эквивалентно вложенной for петли. Он будет проходить через каждые кортеж от (1, 1, 1, 1) до (99, 99, 99, 99). Это пропустит нуль, о котором вы, кажется, попросили.

Answer 2

Попробуйте создать декартовы производные диапазонов массивов, чтобы получить индексы.

import itertools 

cprod = itertools.product(range(1, 100, 1), range(1, 100, 1), range(1, 100, 1), range(1, 100, 1)) 
result = sum([a[cp[0]][cp[1] - b[cp[2]][cp[3] for cp in cprod]) 

Answer 3

Это способ быстрее:

(sum(map(sum, a)) - sum(map(sum, b))) * len(a) * len(b) 

Поскольку вы расчета суммы общей разности массивов. Он будет работать в O (n), но ответ Кевина, использующий itertools, находится в O (n^2).

я не доказал это (редактировать: here's a proof outline), протестирован только с помощью двух случайных 100x100 массивов, но это отчасти интуитивно, если вы об этом думаете.

Код, как указано Кевином, предположил, что ваши массивы 100x100 и будут включать в себя 0. Я предположил, что вы просто хотели использовать два массива 100x100 и получили обозначение, немного испорченное - если вы действительно хотите пропустить 0 и не знаете размер массива, то вы можете использовать следующий фрагмент кода вместо:

from itertools import product 

C = 100 

def _sum(arr, a, b): 
    return sum(arr[i][j] for i, j in itertools.product(range(a, b), repeat=2)) 

answer = (_sum(a, 1, C) - _sum(b, 1, C)) * (C-1)**2 

не так красиво, так как мы итерация подматрицы, но все-таки быстро. Если вы хотите использовать numpy, нарезанная версия может быть написана немного более сжато:

import numpy as np 
A = np.array(a, np.int32) 
B = np.array(b, np.int32) 
answer = (np.sum(A[1:100, 1:100]) - np.sum(B[1:100, 1:100])) * 99**2