Карта сайта Kansoftware
НОВОСТИУСЛУГИРЕШЕНИЯКОНТАКТЫ
KANSoftWare

Объединение отсортированных списков с неизвестным порядком

Delphi , Базы данных , Сортировка и Фильтр

Возникла задача объединить несколько отсортированных списков в один, при этом сохранив исходный порядок сортировки, который неизвестен. Например, у нас есть три списка:

Список 1: abcfh

Список 2: bceh

Список 3: cdef

Известно, что эти списки отсортированы, но порядок сортировки неизвестен. Нам нужно объединить эти списки в один, не содержащий дубликатов, и при этом сохранить исходный порядок сортировки. Результат должен быть таким:

abcdefh

Как же нам это сделать?

Подход с использованием топологической сортировки

Одним из подходов к решению этой задачи является использование топологической сортировки. Топологическая сортировка - это линейный порядок элементов Directed Acyclic Graph (DAG), в котором каждый элемент предшествует всем элементам, на которые он ссылается.

Для нашей задачи мы можем представить каждый список как DAG, где элементы списка являются вершинами, а порядок элементов в списке определяет направление ребер. Затем мы объединяем все DAG в один и выполняем топологическую сортировку.

Например, для наших списков мы получим следующий DAG:

[abcfh] -> [bceh] -> [cdef]

При топологической сортировке этого DAG мы получим результат:

abcdefh

Подтвержденный ответ

Ниже приведен пример реализации топологической сортировки на Object Pascal (Delphi) с использованием очереди:

program TopologicalSort;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Generics.Collections;

type
  TGraph = TList<TList<Char>>;

function TopologicalSort(graph: TGraph): TList<Char>;
var
  indegree: TDictionary<Char, Integer>;
  queue: TQueue<Char>;
  result: TList<Char>;
  i, j: Integer;
  vertex: Char;
begin
  result := TList<Char>.Create;
  indegree := TDictionary<Char, Integer>.Create;
  queue := TQueue<Char>.Create;

  // Calculate indegrees
  for i := 0 to graph.Count - 1 do
  begin
    for j := 0 to graph[i].Count - 1 do
    begin
      if indegree.ContainsKey(graph[i][j]) then
        inc(indegree[graph[i][j]])
      else
        indegree.Add(graph[i][j], 1);
    end;
  end;

  // Enqueue all vertices with indegree 0
  for i := 0 to indegree.Count - 1 do
    if indegree.Values[i] = 0 then
      queue.Enqueue(i);

  // Perform BFS
  while not queue.IsEmpty do
  begin
    vertex := queue.Dequeue;
    result.Add(vertex);
    for i := 0 to graph[vertex].Count - 1 do
    begin
      dec(indegree[graph[vertex][i]]);
      if indegree[graph[vertex][i]] = 0 then
        queue.Enqueue(graph[vertex][i]);
    end;
  end;

  if result.Count < indegree.Count then
    raise Exception.Create('Graph contains a cycle');

  Result := result;
end;

var
  graph: TGraph;
begin
  graph := TGraph.Create;
  graph.Add('abcfh');
  graph.Add('bceh');
  graph.Add('cdef');

  Writeln(TopologicalSort(graph).ToString);
end.

Альтернативный ответ

Еще один подход к решению этой задачи заключается в использовании графа, где элементы списка являются вершинами, а порядок элементов в списке определяет направление ребер. Затем мы объединяем все графы в один и выполняем обход в глубину (DFS) для поиска топологической сортировки.

Пример реализации этого подхода на Object Pascal (Delphi) приведен ниже:

program TopologicalSortDFS;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Generics.Collections;

type
  TGraph = TList<TList<Char>>;

function TopologicalSort(graph: TGraph): TList<Char>;
var
  visited, stack: TList<Char>;
  i, j: Integer;
  vertex: Char;
begin
  visited := TList<Char>.Create;
  stack := TList<Char>.Create;

  // Perform DFS
  for i := 0 to graph.Count - 1 do
  begin
    if not visited.Contains(graph[i][0]) then
      Visit(graph, visited, stack, graph[i][0]);
  end;

  Result := stack.Reverse;
end;

procedure Visit(graph: TGraph; var visited, stack: TList<Char>; vertex: Char);
var
  i: Integer;
begin
  visited.Add(vertex);
  for i := 1 to graph[vertex].Count - 1 do
  begin
    if not visited.Contains(graph[vertex][i]) then
      Visit(graph, visited, stack, graph[vertex][i]);
  end;
  stack.Add(vertex);
end;

var
  graph: TGraph;
begin
  graph := TGraph.Create;
  graph.Add('abcfh');
  graph.Add('bceh');
  graph.Add('cdef');

  Writeln(TopologicalSort(graph).ToString);
end.

Заключение

В данной статье мы рассмотрели задачу объединения отсортированных списков с неизвестным порядком. Мы предложили два подхода к решению этой задачи: использование топологической сортировки и обход в глубину графа. Мы также предоставили примеры реализации этих подходов на Object Pascal (Delphi).

Создано по материалам из источника по ссылке.

Задача состоит в объединении нескольких отсортированных списков в один, сохраняя исходный порядок сортировки, который неизвестен.


Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS




Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.


:: Главная :: Сортировка и Фильтр ::


реклама


©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007
Top.Mail.Ru

Время компиляции файла: 2024-12-22 20:14:06
2025-07-26 02:05:17/0.011195182800293/0