Нахождение N ближайших номеров

Question

Иметь 2-мерный массив, как -

 
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 

Answer 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), но это всего лишь предположение.

Answer 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] 
    next@(val,ind) = minimum $ map (\(arr,i) -> (head arr,i)) arrays 
    comb a@(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)] 

Answer 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)