gleiche Zahlenfolgen im Array untersuchen

[Sendrix]

Hallo Ralph,

vielen Dank für Deine Hilfe. Leider komme ich nicht ganz klar mit Deiner Lösung.
Ich verstehe das so.

Du legst eine Stringliste an und gehst für jedes Element des Arrays der Tiefe entsprechend durch das Array und hängst die Elemente in der Kettenliste aneinander.
Dann überprüfst Du in InListe ob die Kette in der Kettenliste schon vorhanden ist. Wenn nein dann schreibst Du Kette in die Kettenliste.

Ich versteh das so nicht ganz, könntest Du mir das bitte ein wenig erklären?

Sendrix(Sebastian)

[Sendrix]

Hallo FredlFesl,

Danke für Deine Frage, hab ich nicht genau formuliert, sorry. Mir geht es schon darum die längste zusammenhängende, identische Folge herauszufinden.
Das wäre dann also 2 x 1234.

Die, ich nenne Sie mal Zwischenfolgen oder Tiefe (2 x 12 oder 2 x 23 ...) sollen nur dann "erkannt" werden wenn die "Tiefe" bei z.B. 2 oder 3 gleichen aufeinanderfolgenden Elementen beendet werden soll.
Grundsätzlich gilt (1234), also soviele Elemente wie identisch sind, alles andre ist erstmal optional. Mit der Option der variablen Tiefe hab ich es überhaupt noch nicht hinbekommen. Bisher hab ich lediglich geschafft 2 in Folge vorkommende Elemente nochmal im Array zu finden. Bei mehr wie 2 endet es für mich im Schleifenwirrwarr.

Gruß
Sendrix

[Sendrix]

Hallo K-H,

Danke für Deinen Beitrag. Wenn ich das richtig verstehe läuft Dein Vergleich auf den Index des Array hinaus. Es geht aber nicht um den gleichen Index sondern um die gleichen Elemente des Arrays. Es kann ja sein das die Zahlenfolge 1 2 3 4 irgendwo im Array nochmal vorkommt und das herauszufinden ist mein Ziel.

Vieel Grüße,
Sendrix

[BoolString]

Das große Problem ist tatsächlich, wenn man Sequenzen hat, die als Teilsequenzen in einer größeren wieder auftauchen. Das ist ein Standardproblem, z.B. in der Genetik und ein weites Forschungsfeld. Letztlich ist eine visuelle Kontrolle immer ein sehr gutes Hilfsmittel. Ein hier verwendetes Verfahren nennt sich Dot-Plot und sollte nicht mit der gleichnamigen Darstellungsmethode verwechselt werden. Ein paar Algorithmen und Spielzeuge hierzu findest du bei mir unter:

- Hintergrund und Algos
- Software zum Ausprobieren


Für numerische Sequenzen gibt es eine sehr gute Arbeit von Marwan und Co.:

- Recurrence plots
- Graphische Darstellung

Ist vermutlich nicht genau das, was du suchtest, aber vielleicht etwas zum weiter drüber nachdenken/nutzen...

Jan

[ibp]

2 Ideen:
1) Wie wäre es denn, wenn du einfach aufeinanderfolgende Sequenzen (n,n+1,n+2,..,n+k) aus deiner Folge in eine gesonderte Liste schreibst, diese sortierst und dann untersuchst?

2) Bitmasken könnte auch eine Überlegung Wert sein!

[blauweiss]

Hab's doch mal eben implementiert, weil es mich selber interessiert hat.

Delphi-Quellcode:

function GetStringFromHere(aList: TStringList;
                           StartIndex, TokenCount: integer): string;
var
  i: integer;
begin
  Result := aList[StartIndex]; // Achtung keine Abprüfung auf < 0 oder > aList.Count-1 ...!!
  for i := StartIndex+1 to StartIndex+TokenCount-1 do
    if (i > aList.Count-1) then
      break
    else
      Result := Result + aList[i];
end;

function GetMatchIndex(aList: TStringList;
                       OriginIndex, TokenCount: integer): integer;
var
  s: string;
  i: integer;
begin
  Result := -1;
  s := GetStringFromHere(aList, OriginIndex, TokenCount);
  for i := 0 to aList.Count-1 do
    if (i <> OriginIndex) then
      if (s = GetStringFromHere(aList, i, TokenCount)) then
        begin
          Result := i;
          break;
        end;
end;

function GetAnyMatchIndex(aList: TStringList;
                          TokenCount: integer): integer;
var
  i: integer;
begin
  Result := -1;
  for i := 0 to aList.Count-1 do
    if (GetMatchIndex(aList, i, TokenCount) <> -1) then
      begin
        Result := i;
        break;
      end;
end;

function FindBiggestMatch(aList: TStringList): integer;
var
  TokenCount: integer;
  MatchIndex: integer;
begin
  Result := 0;
  TokenCount := Length(aList.Text);
  while (TokenCount >= 1) do
    begin
      MatchIndex := GetAnyMatchIndex(aList, TokenCount);
      if (MatchIndex <> -1) then
        begin
          ShowMessage('Größter Match "' + GetStringFromHere(aList, MatchIndex, TokenCount) +
                      '" bei Index ' + IntToStr(MatchIndex) + #13#10 +
                      'Anzahl Zeichen: ' + IntToStr(TokenCount));
          Result := TokenCount;
          break;
        end;
      dec(TokenCount);
    end;
end;

Aufruf z.B.:

Delphi-Quellcode:

  aList := TStringList.Create;
  // aList füllen ... try..except sparen oder auch nicht
  if (FindBiggestMatch(aList) < 1) then
    ShowMessage('Keine Matches gefunden');
  aList.Free;

Gruß
blauweiss

[Klaus01]

Guten Abend,

würde es denn nicht auch schon ausreichen, wenn maximal nach einer 2 Ziffernfolge sucht
und das Array damit in Einzelschritten absucht.

In der angehängten Grafik wird deutlich, dass damit auch größere zusammenhängende Ziffernfolgen finden kann.

Grüße
Klaus

[blauweiss]

Hallo Sendrix,

ich würde es folgendermaßen angehen:

1. eine Routine (Funktion bzw. Methode falls Du ein Objekt daraus machen willst) "GetStringFromHere"
function GetStringFromHere(StartIndex, TokenCount: integer): string;
-> liefert Konkatenation von "TokenCount" Bestandteilen (natürlich beschränkt durch Listenende) ab StartIndex in der Liste

2. eine Routine "GetMatchIndex"
function GetMatchIndex(OriginIndex, TokenCount: integer): integer;
-> for-Schleife über alle Indizes (OriginIndex aussparen!), Abprüfung auf Gleichheit via GetStringFromHere
-> liefert -1 für keinen Match, ansonsten den Index des Matches

3. eine Routine "GetAnyMatchIndex"
function GetAnyMatchIndex(TokenCount: integer): integer;
-> for-Schleife über alle Indizes, Abprüfung auf Match via GetMatchIndex(Laufvariable, TokenCount)

3. eine Routine "FindBiggestMatch"
function FindBiggestMatch(aList: TStringList): integer;
-> Start mit TokenCount auf großem Wert (aList.Count falls je nur 1 Buchstabe, sonst irgendwas sinnvoll Großes (maximal Length(aList.Text))
-> per while-Schleife runter(!)zählen, um auf Match zu prüfen via GetAnyMatchIndex(TokenCount)

Die Implementation überlasse ich Dir, dürfte ja unschwer sein...

Gruß
blauweiss

[Bjoerk]

Hab auch noch einen:

Delphi-Quellcode:

function FindSubList (const SubList, List: TStringList; const 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;
  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 Result:= B;
    end;
    Inc(I);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  SubList, List: TStringList;
  I, J, K, N, A: integer;
  Result: string;
begin
  N:= 0;
  Result:= '';

  List:= TStringList.Create;
  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');

  SubList:= TStringList.Create;
  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]);
      A:= FindSubList(SubList, List, J);
      if A > N then
      begin
        N:= A;
        Result:= SubList.Text;
      end;
    end;
  SubList.Free;

  List.Free;

  ShowMessage ('Tiefe= '+IntToStr(N)+#13+Result);
end;

[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)