Поиск N ближайших номеров

У вас есть двумерный массив, например -

a[0] = [ 0 , 4 , 9 ]
a[1] = [ 2 , 6 , 11 ]
a[2] = [ 3 , 8 , 13 ]
a[3] = [ 7 , 12 ]

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

Ответ на сказанное выше будет = [ 9 , 6 , 8 , 7 ].

Сделали алгоритм, но не чувствуем его хорошего. Что было бы эффективным алгоритмом для этого с точки зрения сложности времени и пространства?

EDIT - Мой алгоритм (в python) - 

INPUT - Dictionary : table{}
OUTPUT - Dictionary : low_table{}
#
N = len(table)
for word_key in table:
    for init in table[word_key]:
        temp_table = copy.copy(table)
        del temp_table[word_key]
        per_init = copy.copy(init)
        low_table[init]=[]
        for ite in range(N-1):
            min_val = 9999
            for i in temp_table:
                for nums in temp_table[i]:
                    if min_val > abs(init-nums):
                        min_val = abs(init-nums)
                        del_num = i
                        next_num = nums
            low_table[per_init].append(next_num)
            init = (init+next_num)/2
            del temp_table[del_num]
lowest_val = 99
lowest_set = []
for x in low_table:
    low_table[x].append(x)
    low_table[x].sort()
    mini = low_table[x][-1]-low_table[x][0]
    if mini < lowest_val:
        lowest_val = mini
        lowest_set = low_table[x]
print lowest_set

Ответы

Ответ 1

собрать все значения для создания одной упорядоченной последовательности, причем каждый элемент помечен массивом, из которого он пришел: 0 (0), 2 (1), 3 (2), 4 (0), 6 (1),... 12 (3), 13 (2)

затем создайте окно через них, начиная с первого (0 (0)) и заканчивая его в первой позиции, которая заставляет окно охватывать все массивы (0 (0) → 7 (3))

тогда сверните это окно, увеличив начало окна на единицу и увеличив его до конца, пока не появится окно, которое охватывает все элементы.

затем снова сверните его: (2 (1), 3 (2), 4 (0),... 7 (3)) и т.д.

на каждом шаге следить за разницей между самыми большими и наименьшими. В конце концов вы найдете ту, которая находится в самом маленьком окне. У меня такое чувство, что в худшем случае это O (n ^ 2), но это просто предположение.

Ответ 2

Дословная версия алгоритма Haskell с помощью whiterook6:

import Data.List (minimumBy,sortBy)
import qualified Data.Map as M (fromList,toList,adjust,lookup)

f arrays = g (zip arrays [1..]) [] h [(100,0),(0,0)] where
  n = length arrays
  h = (M.fromList $ zip [1..n] (repeat 0))
  g arrays sequence indexes best
    | any ((==0) . snd) (M.toList indexes) = 
        g (foldr comb [] arrays) (next:sequence) (M.adjust (+1) ind indexes) best
    | otherwise = 
        if null (drop 1 arrays) 
           then best'
           else g (foldr comb [] arrays) 
                  (next:init trimmedSequence) 
                  (foldr (M.adjust (+1)) h (ind : (map snd $ init trimmedSequence))) 
                  best'
   where 
     best' = minimumBy comp [best,trimmedSequence]
     [email protected](val,ind) = minimum $ map (\(arr,i) -> (head arr,i)) arrays
     comb [email protected](seq,i) b = if i == ind 
                           then if null (drop 1 seq) 
                                   then b 
                                   else (drop 1 seq,i) : b 
                           else a : b
     comp a b = compare (fst (head a) - fst (last a)) (fst (head b) - fst (last b))
     trimSequence []     _ = []
     trimSequence (x:xs) h
       | any ((==0) . snd) (M.toList h) = 
           case M.lookup (snd x) h of
             Just 0     -> x : trimSequence xs (M.adjust (+1) (snd x) h)
             otherwise  -> trimSequence xs h
       | otherwise                      = []
     trimmedSequence = trimSequence sequence (M.fromList $ zip [1..n] (repeat 0))

Вывод:

*Main> f [[0,4,9],[2,6,11],[3,8,13],[7,12]]
[(9,1),(8,3),(7,4),(6,2)]

Ответ 3

У меня есть вариант алгоритма whiterook, который, по моему мнению, проще (и, кроме начального шага сортировки, он более четко O (N)).

Итерация minval через все значения по порядку. При этом мы сохраняем индекс наименьшего значения в каждом массиве, который больше или равен minval). Мы также сохраняем максимальное значение элементов в этом индексе в своих соответствующих массивах.

Когда мы рассмотрели какой-то конкретный minval, мы можем увеличить индекс для всех массивов, содержащих minval, и при необходимости обновить maxval.

Вот реализация. Обратите внимание, что (за исключением начальной сортировки) это O (N), потому что внутренний цикл выполняется не более одного раза за каждое значение в каждом массиве.

def minspan(aa):
    allnums = sorted(set(sum(aa, [])))
    ntoi = dict((x, []) for x in allnums)
    for i in xrange(len(aa)):
        for x in aa[i]:
            ntoi[x].append(i)
    indexes = [0] * len(aa)
    maxval = max(a[0] for a in aa)
    best = None
    for minval in allnums:
        if best is None or best[0] > maxval - minval:
            best = maxval - minval, minval, maxval
        for i in ntoi[minval]:
            indexes[i] += 1
            if indexes[i] >= len(aa[i]):
                return [min(x for x in a if x >= best[1]) for a in aa]
            maxval = max(maxval, aa[i][indexes[i]])

aa = [[0,4,9], [2,6,11], [3,8,13], [7,12]]
print minspan(aa)