Algorithmen um Listen abzugleichen

[freimatz]

Hallo zusammen,
"Algorithmen, Datenstrukturen und Klassendesign" - mir geht hier um Algorithmen. Falls jemand Lust auf Knobeleien hat, freue ich mich auf Anregungen.

Gegeben sei ein ordinaler Typ. Das wäre konkret ein Aufzählungstyp, ich nehme hier einfach mal Buchstaben. Die Anzahl ist typischerweise ca. 50.
Zu diesem Typ gibt es Listen. Das kann ein Array, TList oder IList sein. Die Reihenfolge ist aber wichtig.

Gesucht wird (zuerst mal) ein Algorithmus mit dem man prüfen kann ob die Reihenfolge einer Liste stimmt anhand einer anderen Liste. Beispiel:
Referenzliste: (a,d,e,c,b)
Beispiele für Ok-Fälle: (a,c,b), (a,d,e,c,b), (), (c,b)
Beispiele für Ko-Fälle: (a,b,a), (a,a,c)

(Bitte keine "Kanonen" wie TStringList, TMemTable oder ähnlichem :mrgreen:)

[himitsu]

Nja, im Grunde mußt du doch nur deine "Liste" von Anfang bis Ende durchlaufen. (z.B. For-Schleife)
Und da prüfst du dann jeweils, ob bei zwei aufeinanderfolgende "Items" die Indize (der ordinale Wert) größer werden, als dessen Vorgänger.
Bei gleich oder kleiner, ist es "nicht OK".

[freimatz]

Hm, weis nicht ob ich Dich richtig verstehe... Vielleicht liegt es daran dass ich in dem Beispiel keinen Typ angegeben habe. Der wäre z.B. TBla = (a,b,c,d,e,f,g)
Die Referenzliste ist in dem Beispiel: (a,d,e,c,b).
Die ordinalen Werte wären dann: 1,4,5,3,2.
Bei dem Ok-Fall (a,c,b) wäre die dann 1,3,2 - und somit nicht aufsteigend.

Aber man könnte ja vor der Prüfung eines Falles, die Werte umrechnen in die Position wo sie in der Referenzliste sind.

[Gausi]

Einfach so runtergeschrieben:

Delphi-Quellcode:

function TestListIsValid(TestListe, ReferenzListe: TSomeList): boolean;
var
  idxR, idxT: Integer;
begin
  idxR := 0;
  idxT := 0;

  // Hauptschleife: Die Testliste durchgehen
  while (idxT <= TestListe.Count - 1) and (idxR <= ReferenzListe.Count - 1) do begin
    // nächste Übereinstimmung in der Referenzliste suchen
    while (TestListe[idxT] <> ReferenzListe[idxR]) and (idxR < ReferenzListe.Count - 1) do
      inc(idxR);

    if TestListe[idxT] = ReferenzListe[idxR] then begin
      // Übereinstimmung gefunden, in beiden Listen eins weiter gehen
      inc(idxT);
      inc(idxR);
    end;
  end;

  // Die Testliste passt, wenn man die Testliste komplett durchlaufen hat.
  Result := idxT = TestListe.Count;
end;

Laufzeit: Linear in der Länge der Listen.