У меня есть n упорядоченных списков неравного размера (где я заранее не знаю, сколько будет списков). Мне нужно найти минимальное среднее расстояние между одним элементом в каждом списке.
Например, если n = 3 для трех списков:
a = [14, 22, 36, 48]
b = [14, 23, 30, 72]
c = [1, 18, 24]
Выход должен быть (22,23,24), потому что:
mean(abs(22-23), abs(23-24), abs(22-24)) = 1.33333
, что является наименьшим из всех точек в приведенном выше примере.
Я попытался реализовать его в Python следующим образом
def aligner(aoa):
'''
read arrays of arrays of peaks and return closest peaks
'''
#one of arrays is empty
if not [y for x in aoa for y in x]:
return None
# there is the same nr in all array no need to do anything
candidate = set.intersection(*map(set, aoa))
if candidate:
# returns intersect
return [max(list(candidate))] * len(aoa)
else:
#tried cartesian product via bumpy malloc err
pass
Теперь я сомневаюсь в реализации другой части. Я думал об использовании декартового произведения для генерации всех комбинаций, но у меня возникают проблемы с памятью. Мои предположения будут состоять в том, чтобы сгенерировать всю комбинацию каким-либо образом (может быть, itertools ??) и пройтись по всем этим, но я не знаю, есть ли какой-нибудь алгоритм, который решает эту проблему, который я мог бы использовать.
Мне не нужен код, я только намекаю, есть ли какой-нибудь эффективный способ решения этой проблемы, или грубая сила с n для циклов в перестановочных списках - единственный
EDIT
Что касается размера проблемы, то nr списка максимум 100 (фиксированный), в то время как nr элементов может варьироваться, но я бы сказал, что представленный пример с 4 или 5 точками в списке является реалистичным сценарием.
Все точки неотрицательны.
Попробовал предлагаемое решение itertools, но, конечно, не проблемы с памятью, но он работает часами, и он застрял на 3-м элементе.