Пересечение диапазона / объединение

Question

Я разрабатываю язык программирования, для которого я хочу предоставить тип данных Range , который на данный момент представляет собой, как обычно, список пар int значений (x,y) с ограничением что x < y. Я говорю не так, как обычно, потому что обычно диапазон - это просто пара, но в моем случае он больше чем, что позволяет иметь, например,

1 to 5, 7 to 11, 13 to 22

все содержится в одном объекте.

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

1 to 5 || 3 to 8 = 1 to 8
1 to 5 && 3 to 8 = 3 to 5
(1 to 3, 4 to 8) && 2 to 6 = (2 to 3, 4 to 6)

, где || - объединение, а && - пересечение.

На данный момент их реализация, как указывалось ранее, является просто списком. Я знаю, что существует более подходящая структура данных (интервальное дерево), но сейчас я более заинтересован в создании новых списков из объединения / пересечения других списки ..

Каковы современные алгоритмы для реализации этих двух функций?

Заранее спасибо

Answer 1

Поскольку вы не хотите иметь дело с деревьями интервалов и использовать только списки, я бы посоветовал вам сохранить представление диапазона в виде списка непересекающихся интервалов, отсортированных по координатам x.

Имея два списка, вы можете вычислить объединение и пересечение, выполнив шаг слияния, как мы это делаем при слиянии отсортированных списков.

Пример:

Для объединения L1 и L2:

Создать L как пустой список.

Возьмите интервал с наименьшим x из L1 и L2 и поместите в L.

Теперь возьмите наименьшее снова, сравните с последним элементом L и решите, нужно ли их объединить (если они перекрываются) или добавить новый интервал (если они не перекрываются) в конце L и продолжить обработку, как мы делаем слияние двух отсортированных списков.

Как только вы закончите, L будет объединением, чьи интервалы отсортированы по x и не пересекаются.

Для пересечения вы можете сделать нечто подобное.

Answer 2

Мне кажется, что лучший способ хранения интервалов - деревьев интервалов - это также средство для выполнения операций над ними. Поскольку выполнение пересечений дерева точек является основным случаем, поддерживаемым запросом дерева интервалов, кажется, что его не слишком сложно расширить до пересечения интервалов: для каждого интервала в tree1 запрос tree2 для обеих конечных точек. Для пересечения вычтите пересекающийся интервал из tree1, а для объединения добавьте пересекающийся интервал. Для каждой операции вычитания / сложения вы получите новый набор интервалов для добавления к вашему новому tree3, который в итоге станет результатом вашей операции.

Answer 3

без интервальных деревьев ..... Никаких специальных заказов не требуется ... Вероятно, не "состояние дел":)

        (* "{ ... }" means "list" *)

function Union [{x1_,x2_},{y1_,y2_}] := 

      if {x1,x2}=={} then {x1,x2}={y1,y2} (* This is needed because the intersection *)
      if {y1,y2}=={} then {y1,y2}={x1,x2} (* may return an empty interval *)
                                          (* so, empty intervals need this code *)

      if {y1,y2}=={} then return[{}]      (* Both intervals were empty! *)

      if Min[x1,x2] > Min[y1,y2] 
      then   
          return[Union[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)
              return[{{x1,x2},{y1,y2}}]
          else                       (* Overlapping intervals *)
              return[{Min[x1,x2],Max[x1,x2,y1,y2]}]

end function <Union>                      

function Intersection  [{x1_,x2_},{y1_,y2_}] := 

      if ({x1,x2}=={} OR {y1,y2}=={}) then return[{}] (* empty intervals do exist *)

      if Min[x1,x2] > Min[y1,y2]
      then   
          return[Intersection[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)

              return[{}]             (* HERE we create an empty interval*)

          else                       (* Overlapping intervals *)

              return[{Min[y1,y2],Min[Max[x1,x2],Max[y1,y2]]}]

end function <Intersection>

Edit>

Возможно, обобщение на n аргументов лучше, чем диадические функции.

Что-то вроде> (извините за нестандартный псевдокод)

        function GenUnion[{L:list of intervals}]:=

                 if (Tail[L] is interval)
                     return[Union[Head[L],Tail[L]]]
                 else                                                            
                     return[Union[Head[L], GenUnion[Head[Tail[L]],Tail[Tail[L]]]  

        end function <GenUnion>

Answer 4

Я пока опубликую свою собственную реализацию (только операция объединения), я использую функциональный язык, поэтому будьте осторожны ... это может сбить с толку:

let rec calc c l1 l2 =
  match c,l1,l2 with                            
    None, (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> calc (Some (f1,t1)) y1 n2
    | None, n1, (f2,t2) :: y2 -> calc (Some (f2,t2)) n1 y2
    | None, _, _ -> []
    | (Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2
    | (Some (fc,tc) as cur), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when t2 <= fc -> calc cur n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 <= tc && t1 > fc -> calc (Some (fc,t1)) y1 n2
    | Some (fc,tc), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when f2 <= tc && t2 > fc -> calc (Some (fc,t2)) n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> [fc,tc] @ calc (Some (f1,t1)) y1 n2
    | Some (fc,tc), (t :: e as n1), (f2,t2) :: y2 -> [fc,tc] @ calc (Some (f2,t2)) n1 y2
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t > tc -> calc (Some (fc,t)) [] tr
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t <= tc -> calc (Some (fc,tc)) [] tr
    | Some (fc,tc), [], x -> [fc,tc] @ x
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t > tc -> calc (Some (fc,t)) tr []
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t <= tc -> calc (Some (fc,tc)) tr []
    | Some (fc,tc), x, [] -> [fc,tc] @ x

Используется cаргумент для хранения текущего интервала (на котором перекрываются диапазоны слияния), в то время как l1 и l2 являются двумя int*int list.

Синтаксис прост, каждая строка представляет отдельный случай, который имеет c, l1 и l2 указаны точно.Позвольте привести несколько примеров:

(Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2

У меня есть текущий диапазон fc,tc, и в двух списках есть хотя бы один элемент (поэтому (f1,t1)::y1), поэтому, если t1 <= fc, тодиапазон первого списка заканчивается перед текущим, и я могу быть отброшен, поэтому он рекурсивно вызывает себя с таким же диапазоном cur, y1, в котором отбрасывается первый, и n2, который является псевдонимом для того же списка, полученного какАргумент.

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

Answer 5

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

Если это так, вы можете просто "сжать их":

1. Возьмите интервал, который начинается раньше
2. Если следующий интервал из диапазона other начинается после его окончания, выведите этот интервал и перейдите к 1
3. Если следующийинтервал из диапазона other заканчивается до этого, отменить этот другой интервал и перейти к 2
4. Установить начало другого интервала равным началу этого интервала, отменить этот интервал и перейти к1

После этого вы можете выполнить и объединить соседние интервалы, если это необходимо.

Может быть доступна некоторая незначительная оптимизация, но в основном она реализует операцию объединения и должна показывать общий процесс дляреализации пересечения.