gleiche Zahlenfolgen im Array untersuchen

[p80286]

so mal in unreine gedacht,
nimm zwei pointer und laß beide über Deine datenmenge laufen ungefähr so etwas:

Delphi-Quellcode:

p1,p2:^array[0..4] of char;

p1:=@Array[0];
p2:=@array[sucheindexgleich];
if p1^=p2^ then showmessage"Gleiche werte gefunden"

Gruß
K-H

[FredlFesl]

Was ist mit der Sequence
1 2 3 4 1 2 3 4

Welches Ergebnis willst Du?
1234 kommt 2x vor (also nur die längste Subsequenz),
oder
12 kommt 2x vor,
23 kommt 2x vor
34 kommt 2x vor
123 kommt 2x vor
234 kommt 2x vor
1234 kommt 2x vor (also alle Subsequenzen)?

[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

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