gleiche Zahlenfolgen im Array untersuchen

[Sendrix]

Hallo,

vielen Dank für eure rege Beteiligung. Ich mußte das ein oder andere im Netz erstmal nachlesen um überhaupt verstehen zu können was sich dahinter verbirgt.

Zur Frage von Jumpy aus Beitrag #25 : Es soll tatsächlich mit dem nächsten Element fortgefahren werden, also Element für Element, in Deinem Beitrag Möglichkeit B. Wenn aber eine Folge eine (kleinere)Teilfolge einer anderen, bereits vorhandenen Folge ist, was im unteren Beispiel von Jumpy bei elementweiser vorgehensweise so wäre, dann ist diese Teilfolge nicht relevant.

Ich bleibe beim Beispiel von Jumpy:
1 2 3 4 9 8 7 1 2 3 4 6 2 3 4 9 8 7

1234 -> 1234
234987 -> 234987
34987 -> 34987 TeilFolge von 234987 damit nicht relevant
4987 -> 4987 TeilFolge von 234987 damit nicht relevant
987 -> 987 TeilFolge von 234987 damit nicht relevant
87 - > 87 TeilFolge von 234987 damit nicht relevant

weiter mit der 7 -> Keine Folge
weiter mit der 1 -> Keine Folge

234 -> 234 TeilFolge von 234987 damit nicht relevant
34 -> 34 TeilFolge von 234987 damit nicht relevant

weiter mit der 4 -> Keine Folge
weiter mit der 6 -> Keine Folge
weiter mit der 2 -> Keine Folge
weiter mit der 3 -> Keine Folge
weiter mit der 4 -> Keine Folge
weiter mit der 9 -> Keine Folge
weiter mit der 8 -> Keine Folge
weiter mit der 7 -> Keine Folge


In dem Beispiel liegen also effektiv 2 Folgen vor.
Es soll so lange gesucht werden bis sich die Folgen nicht mehr gleichen. Suche immer nur in eine Richtung.

Danke auch für den Sourecode. Die schaue ich mir alle an und lerne dabei auch ne Menge. Den SoureCode von Sir Rufo muß ich erst noch ein wenig anpassen da ich noch mit Delphi 5 arbeite. Beim Code von blauweis hab ich festgestellt das er sehr lange sucht und auch findet was er soll, irgendwo hab ich da eventuell auch einen Fehler eingebaut glaube ich, bei Array > 250 Elemente gehts bei mir nicht weiter und das Programm kommt nicht zurück. Den letzten Code von Bjoerk schau ich mir noch an. Ich muß dazu sagen das ich die Codes damit nicht bewerten möchte, das könnte ich gar nicht beurteilen, ich wollte damit nur ausdrücken das ich mich intensiv damit beschäftige und dabei verschiedene Methodenkennenlerne.

Vielen Dank und schönes Wochenende,
Sendrix(Sebastian)

[Bjoerk]

Wenn du alle Results haben möchtest, dann kann man z.B. die bereits gefundenen aus der Liste rauslöschen.

Delphi-Quellcode:

function FindSubList(const SubList, List: TStringList; var Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= List.Count;
  B:= SubList.Count;
  I:= Index;
  if I < 0 then Exit;
  if B = 0 then Exit;
  if B > A then Exit;
  while (Result = 0) and (I <= A-B) do
  begin
    J:= 0;
    if (List[I] = SubList[J]) then
    begin
      while (J < B-1) and (List[I+J+1] = SubList[J+1]) do Inc(J);
      if J = B-1 then
      begin
        Result:= B;
        Index:= I;
      end;
    end;
    Inc(I);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  SubList, List: TStringList;
  I, J, K, N, N1, J1, Index: integer;
  Result: string;
  done: boolean;
begin
  List:= TStringList.Create;
  SubList:= TStringList.Create;
  try
    List.Add('1');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('9');
    List.Add('8');
    List.Add('7');
    List.Add('1');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('6');
    List.Add('2');
    List.Add('3');
    List.Add('4');
    List.Add('9');
    List.Add('8');
    List.Add('7');
    repeat
      N:= 1;
      Result:= '';
      for I:= 0 to List.Count-2 do
        for J:= I+1 to List.Count-1 do
        begin
          SubList.Clear;
          for K:= I to J do SubList.Add(List[K]);
          J1:= J;
          N1:= FindSubList(SubList, List, J1);
          if N1 > N then
          begin
            N:= N1;
            Index:= J1;
            Result:= SubList.Text;
          end;
        end;
      done:= true;
      if N > 1 then
      begin
        ShowMessage('Tiefe= '+IntToStr(N)+#13+Result);
        done:= false;
        for I:= Index to N+Index-1 do List.Delete(Index);
      end;
    until done;
  finally
    List.Free;
    SubList.Free;
  end;
end;

[Sendrix]

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
Sendrix

Noch was anderes:
Immer wenn ich mich im Forum anmelde und auf einen Beitrag antworten möchte lande ich wieder bei der Anmeldung obwohl ich bereits in der OnlineListe zu sehn bin. Irgendwann wenn ich dann zum x ten mal auf Anmelden geklickt hab klappts dann.

[Bjoerk]

Zitat von Sendrix:

Hallo Bjoerk,

Danke für den Source. Probleme hab ich mit dem Verständnis, dem Nachvollziehen der Funktion FindSubList. Wie kommt man auf sowas ? Mir ist das bisher nicht gelungen gedanklich nachzubauen. Funktionieren tut's sehr gut nur kapier ich es nicht ganz und frage mich wie man auf so einen Algorithmus kommt.
Kannst Du mir dazu eventuell ein paar Zeilen zum besseren Verständnis schreiben ?

Danke,

Viele Grüße,
Sendrix

Ist nichts anders als PosEx, jedoch bei 0 statt 1 beginnend und für Stringlisten statt für Strings .

Versuche vielleicht deshalb erst die normale PosEx zu verstehen (ist etwas anschaulicher und fast das gleiche).

Delphi-Quellcode:

function PosEx (const Substr, S: string; const Index: integer): integer;
var
  I, J, A, B: integer;
begin
  Result:= 0;
  A:= Length(S);
  B:= Length(Substr);
  I:= Index;
  if I < 1 then Exit;
  if B = 0 then Exit;
  if B > A then Exit;
  while (Result = 0) and (I <= A-B+1) do
  begin
    J:= 1;
    if S[I] = Substr[J] then
    begin
      while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J);
      if J = B then Result:= I;
    end;
    Inc(I);
  end;
end;

Fange bei I an. J ist zunächst 1. Wenn das I. Zeichen von S mit dem (immer) 1. Zeichen von Substr übereinstimmt, dann hast du eine Chance, Substr zu finden [if S[I] = Substr[J] then]. Probiere dann, ob weitere Zeichen von S und Substr auch übereistimmen. Ansonsten mache an der I+1. Position von S weiter und probiere das selbe, solange, bis Substr nicht mehr in S reinpasst oder du ein Ergebnis ungleich Null hast [while (Result = 0) and (I <= A-B+1) do]. Wenn das Ergebnis Null ist, konnte der Sustr nicht gefunden werden. (Man setzt in der Regel Result vorab auf Null, wenn mögliche Ergebnisse bei 1 beginnen, auf -1, wenn mögliche Ergebnisse ab 0 möglich sind.)

Wenn also das I. Zeichen von S mit dem 1. Zeichen von Substr übereinstimmt, dann mache folgendes (J ist immer noch 1): Ist das I+J. Zeichen von S mit dem J+1. Zeichen von Substr identisch, dann erhöhe J um eins. J ist dann also J+1. Mache das ganze solange, wie dieser Vergleich gelingt oder das letzte Zeichen von Substr erreicht ist [while (J < B) and (S[I+J] = Substr[J+1]) do Inc(J)]. Ist diese Bedingung B-1 mal erfüllt, das erste Zeichen haben wir bereits vorher abgefragt, dann ist J gleich B (Länge von Substr). In diesem Falle hast du Substr gefunden. Gib als Ergebnis die Stelle zurück, wo die erfolgreiche Suche begonnen hat [if J = B then Result:= I]. Result ist jetzt nicht mehr Null und die function wird beendet.

[Sendrix]

Hallo Bjoerk,

jetzt hab ich es kapiert. Der hinweis auf PosEx war wirklich hilfreich. Das hab ich mir genau angesehn und konnte es dann mit Deiner beschreibung gut auf Deinen Sourcecode übertragen und verstehn. So langsam komme ich weiter. Danke für Deine / Eure Tips und Hilfe.

Sendrix