良い質問です。トポロジカル ソートが最も推奨される方法かもしれませんが、最初に入力を解析して依存関係リストを作成する必要があります。注文の定義を設定するために、複数のリストに含まれるアイテムを見つけることに基づいて、より直接的なアプローチを考えました。
時間の複雑さについては何も予測できませんが、パフォーマンスは気にしないので、特に項目の総数が最大で 500 であることを考慮すると、このアルゴリズムはうまく機能すると思います。
アルゴリズム
- すべてのリストは一時的なリストにまとめられ、すべての重複項目を識別してふるいにかけるために自然に並べ替えられます。Keysという名前のこれらの複製は、最終的な並べ替え順序の唯一の定義を構成します。
- キー リストは、2 つの項目ごとに比較することにより、入力の並べ替え順序で並べ替えられます。2 つのキーが同じ入力リストにある場合、そのリストの最初のキーが出力リストの 2 番目のキーよりも前になります。どの入力リストでも 2 つのキーが同時に発生しない場合、それらは等しいと見なされます。
- その後、ループがキーを循環します。
- サイクルごとに、各入力リスト内で、前のキーと現在のキーの間の各項目が出力リストに追加されます。サイクルは、現在のキーの追加で終了します。
実装
type
TSorterStringList = class(TStringList)
protected
Id: Integer;
KeyId: Integer;
function Current: String;
public
constructor Create;
end;
TSorterStringLists = class(TObjectList)
private
function GetItem(Index: Integer): TSorterStringList;
public
property Items[Index: Integer]: TSorterStringList read GetItem; default;
end;
TSorter = class(TObject)
private
FInput: TSorterStringLists;
FKeys: TStringList;
procedure GenerateKeys;
function IsKey(const S: String): Boolean;
public
constructor Create;
destructor Destroy; override;
procedure Sort(Output: TStrings);
property Input: TSorterStringLists read FInput;
end;
{ TSorterStringList }
constructor TSorterStringList.Create;
begin
inherited Create;
KeyId := -1;
end;
function TSorterStringList.Current: String;
begin
Result := Strings[Id];
end;
{ TSorterStringLists }
function TSorterStringLists.GetItem(Index: Integer): TSorterStringList;
begin
if Index >= Count then
Count := Index + 1;
if inherited Items[Index] = nil then
inherited Items[Index] := TSorterStringList.Create;
Result := TSorterStringList(inherited Items[Index]);
end;
{ TSorter }
constructor TSorter.Create;
begin
inherited Create;
FInput := TSorterStringLists.Create(True);
FKeys := TStringList.Create;
end;
destructor TSorter.Destroy;
begin
FKeys.Free;
FInput.Free;
inherited Destroy;
end;
threadvar
CurrentSorter: TSorter;
function CompareKeys(List: TStringList; Index1, Index2: Integer): Integer;
var
Input: TSorterStringLists;
I: Integer;
J: Integer;
K: Integer;
begin
Result := 0;
Input := CurrentSorter.Input;
for I := 0 to Input.Count - 1 do
begin
J := Input[I].IndexOf(List[Index1]);
K := Input[I].IndexOf(List[Index2]);
if (J > - 1) and (K > -1) then
begin
Result := J - K;
Break;
end;
end;
end;
procedure TSorter.GenerateKeys;
var
All: TStringList;
I: Integer;
begin
All := TStringList.Create;
try
All.Sorted := True;
All.Duplicates := dupAccept;
for I := 0 to FInput.Count - 1 do
All.AddStrings(FInput[I]);
for I := 0 to All.Count - 2 do
if (All[I] = All[I + 1]) then
if (FKeys.Count = 0) or (FKeys[FKeys.Count - 1] <> All[I]) then
FKeys.Add(All[I]);
finally
All.Free;
end;
CurrentSorter := Self;
FKeys.CustomSort(CompareKeys);
end;
function TSorter.IsKey(const S: String): Boolean;
begin
Result := FKeys.IndexOf(S) > -1;
end;
procedure TSorter.Sort(Output: TStrings);
var
KeyId: Integer;
I: Integer;
List: TSorterStringList;
begin
if FInput.Count = 0 then
Exit;
Output.BeginUpdate;
try
GenerateKeys;
for KeyId := -1 to FKeys.Count - 1 do
begin
for I := 0 to FInput.Count - 1 do
begin
List := FInput[I];
if List.KeyId <= KeyId then
while (List.Id < List.Count) and not IsKey(List.Current) do
begin
Output.Add(List.Current);
Inc(List.Id);
end;
while (List.Id < List.Count) and IsKey(List.Current) do
begin
List.KeyId := FKeys.IndexOf(List.Current);
Inc(List.Id);
end;
end;
if KeyId + 1 < FKeys.Count then
Output.Add(FKeys[KeyId + 1]);
end;
finally
Output.EndUpdate;
end;
end;
使用例
procedure TForm1.Button1Click(Sender: TObject);
var
Sorter: TSorter;
begin
Sorter := TSorter.Create;
try
Sorter.Input[0].CommaText := '1, 2, 4, 9, 10, 11, 22, 46, 48, 51, 70, 72';
Sorter.Input[1].CommaText := '3, 9, 23, 43, 44, 45, 47, 48, 51, 71, 90, 91';
Sorter.Input[2].CommaText := '0, 3, 4, 7, 8, 11, 23, 50, 51, 52, 55, 70';
Sorter.Input[3].CommaText := '2, 6, 14, 15, 36, 37, 38, 39, 51, 65, 66, 77';
Sorter.Input[4].CommaText := '5, 27, 120, 130';
ListBox1.Items.Assign(Sorter.Input[0]);
ListBox2.Items.Assign(Sorter.Input[1]);
ListBox3.Items.Assign(Sorter.Input[2]);
ListBox4.Items.Assign(Sorter.Input[3]);
ListBox5.Items.Assign(Sorter.Input[4]);
Sorter.Sort(ListBox6.Items);
// Results in:
// 1, 0, 5, 27, 120, 130, 3, 2, 6, 14, 15, 36, 37, 38, 39, 4, 7, 8, 9, 10,
// 11, 22, 46, 23, 43, 44, 45, 47, 50, 48, 51, 71, 90, 91, 52, 55, 65, 66,
// 77, 70, 72
finally
Sorter.Free;
end;
end;