Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[stoxx]

Ich hab hier ein problem, was ich irgend´wie nicht zufriedenstellend lösen kann und da ich schon einen Knoten im Kopf habe, wollte ich einfach mal fragen.
Ich möchte es mal formulieren.
Ich habe es im Gefühl, dass es da eine schnellere Lösung geben muss, aber komm nicht so recht drauf,... vielleicht täuscht mich auch mein Gefühl.
Das Verfahren hätte normalerweise ein Laufzeitverhalten das proportional zu : n * (n-k) ist
Ziel wäre aber die proportionalität zu n.



ich habe n - Elemente, die auf folgende Art und Weise folgendes Ergebnis liefern sollen.
Ich möchte es mal an einem Beispiel mit 7 Elementen demonstrieren

a ist das gegebene Array und x das Ergebnis Array, dass genauso groß ist wie a.

Delphi-Quellcode:

var a, x : array[1..7] of char;

a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  
m     m     r     f     f     f     a

Als Ergebnis soll rauskommen:

x[1]  x[2]  x[3]  x[4]  x[5]  x[6]  x[7] 
m     m     f     f     f     f     a

Pseudocode:

Delphi-Quellcode:

n := 7;

for i := 0 to 6 do
begin
    
    x[n-i] := 
    Es ist der Buchstabe mit folgenden Eigenschaften:
    1. Derjenige, der von vorn durchgegangen (von x[n-i] bis x[n]) sich über
    den größten bereich erstreckt. 
    Der Bereich für einen Buchstaben ist definiert:  Er beginnt ab dem Index, wo der betreffende 
    Buchstabe am häufigsten vorkommt. 
    und endet bei dem Index , wo ein anderer neuer Buchstabe dessen Häufigkeit übertrifft.
              
end;

Und zwar ... hmmm , ist nicht einfach zu formulieren.

der Witz an der Sache ist, dass x[1] den Buchstaben "m" erhält. und zwar im letzten Schritt (im siebten Schleifendurchlauf bei i = 6 )
Bei jedem Schritt i muss man von vorn bis hinten alle Werte durchsehen.
Bei i = 3 zum Beispiel fängt man bei a[3] an und hört bei a[7] auf um x[3] zu berechnen/zu ermitteln.

Im siebten und letzten Schritt passiert folgndes. ( i= 6 )
Ich gehe in 7 Schritten von a[1] bis a[7]

dabei für j := 1 bis 7
j = 1 -> a[1] -> m kommt einmal vor und erstreckt sich über größten bereich der Länge 1
j = 2 -> a[2] kommt hinzu -> m kommt 2 mal vor und erstreckt sich über einen Bereich der Lange 2
j = 3 -> a[3] kommt hinzu -> m ist immernoch der häufigste Buchstabe ( zweimal) und erstreckt sich nun über einen Bereich von a[1] bis a[3] ... also hat die Bereichsgröße von 3
j = 4 -> a[4] kommt hinzu -> m erstreckt sich nun über einen Bereich von 4, nämlich von a[1] bis a[4]

usw.

bei j = 7 entscheidet sich dann, was in x[1] ( i = 6) eingetragen wird.
nämlich "m", weil "m" sich über einen Bereich von 6 erstreckt. Genauer von a[1] bis a[6].
Da kommt es nämlich als Buchstabe am häufigsten vor, nämlich 2 mal. Buchstabe "f" auch, aber damit "f" das "m" ablösen kann muss es dreimal vorkommen.
Das geschieht bei j = 7, dann ist "f" am Häufigsten, erstreckt sich aber nur über einen Bereich von eins.
Nämlich von a[7] bis a[7]. Da kommmt es dreimal vor. ( mehr als "m").
Obwohl "f" 3 mal vorkommt, also öfter als "m", wird in x[1] "m" eingetragen. Da Länge des Bereichs von "m" 6 beträgt.

r fällt in dem Ergebnisarray ganz raus,

ach heije .......



Jetzt ist die große Frage, wie man das berechnen könnte, in einem Rutsch von hinten nach vorn in 7 Schritten, ohne wieder bei jedem Schritt nach hinten gehen
zu müssen um die Zählung neu anzufangen.

Es ist zulässig, sich irgendwas zu indizieren, da sich a1 bis a7 nicht ändern. Irgendwann kommt a8 hinzu, da wird das Ergebnisarray komplett neu berechnet. Aber habe noch keine Ideen.

*grübel
[edit=SirThornberry]Da ausversehen der Zitieren-Button anstelle des Edit-Buttons verwendet wurde enstanden 2 Beiträge. Somit wurden der erste Beitrag gelöscht und bei dem zitierten (geänderten Beitrag) die Zitiat-Tags entfernt. Mfg, SirThornberry[/edit]

[negaH]

Lass mich mal raten

" m m r t f f f y x x x x x"

müsste

" m f x x x x x x x x x x x"

ergeben ?

Dann ist das einfach. Du arbeitest von vorne nach hinten. Du speicherst den Index an dem der Buchstabe, hier m,f,x im Array gespeichert werden müsste, also m = 1, f = 2, x = 3. Nun brauchst du noch eine Variable die speichert wie oft der aktuell höchste Buchstabe an einem Stück vorkam. Also m = 2, f = 3, x = 5. Bei jedem neuen Buchstaben wird nun ein Zähler auf 1 gesetzt und solange inkrementiert wie der nachfolgende Buchstabe identisch ist. Ist der nachfolgende Buchstabe nicht identisch so vergleichst du diesen Zähle mit dem Zähler des aktuell höchsten Buchstabens. Sollte der Zähler größer sein so passieren zwei Dinge: 1.) im Array am Buchstaben-Index den aktuellen Buschstaben speichern und Buchstaben-Index +1 inkrementieren. 2.) den aktuell höchsten Zähler auf den neuen Wert setzen.

Am Ende hast du ein Array das so assehen würde:

" m f x t f f f y x x x x x"

bei dem aber nur die Werte

" m f x"

von Interesse sind. Die nachfogenden Werte im Array müssen alle mit "x" gefüllt werden.

Gruß Hagen

[marabu]

Guten Morgen.

Nehmen wir mal an, dass die Beispieldaten korrekt sind. Mit dem angegebenen Algorithmus komme ich dann aber zu dem Ergebnis m2f5. Wo ist mein Denkfehler?

Code:

str   m m r t f f f
cnt   1 2 1 1 1 2 3
rng   6 4 3 2 3 2 1  // corr.
new   m m f f f f f

Hagens Beispiel liefert mir das Ergebnis f5x8:

Code:

str   m m r t f f f y x x x x x
cnt   1 2 1 1 1 2 3 1 1 2 3 4 5
rng   6 4 3 2 7 5 3 2 5 4 3 2 1  // corr.
new   f f f f f x x x x x x x x

str ist der Eingabe-String, cnt ist die fortgeschriebene Häufigkeit des aktuellen Buchstaben, rng ist die Größe des Bereichs und new ist der Ergebnis-String.

Grüße vom marabu

[stoxx]

Zitat:

Zitat von negaH

Lass mich mal raten

" m m r t f f f y x x x x x"

müsste

" m f x x x x x x x x x x x"

ergeben ?

Hi Du,

Danke :-) .. ich hatte gehofft, dass Du das Problem vielleicht entdeckst.
das ist nicht richtig, denn z.B. x[5] wird berechnet von a[5] bis a[13], also aus der Sequenz f f f y x x x x x.
Da "f" bis zu a[11] der häufigste Buchstabe ist (nämlich 3 mal), ist dessen Länge der Gültigkeit am längsten ( Länge 7)
Es wird im Prinzip so lange gewertet, solange ein Buchstabe der "Sieger" ist.

Ich versuche heute abend mal ein kleines Beispiel auf Buchtstaben zu basteln, das war nur zur veranschaung. Bei mir im Programm ist das Intern alles mit Listen und Zahlen umgesetzt. Da wäre auch viel zu viel drum rum, um da nochwas erkennen zu können.

[stoxx]

Zitat:

Zitat von marabu

Guten Morgen.

Nehmen wir mal an, dass die Beispieldaten korrekt sind. Mit dem angegebenen Algorithmus komme ich dann aber zu dem Ergebnis m2f5. Wo ist mein Denkfehler?

Code:

str   m m r t f f f
cnt   1 2 1 1 1 2 3
rng   6 4 1 1 3 2 1
new   m m f f f f f

Hagens Beispiel liefert mir das Ergebnis f5x8:

Code:

str   m m r t f f f y x x x x x
cnt   1 2 1 1 1 2 3 1 1 2 3 4 5
rng   6 4 1 1 7 5 3 2 5 4 3 2 1
new   f f f f f x x x x x x x x

str ist der Eingabe-String, cnt ist die fortgeschriebene Häufigkeit des aktuellen Buchstaben, rng ist die Größe des Bereichs und new ist der Ergebnis-String.

Grüße vom marabu

In meinem Beispiel hast Du ein wenig Recht, das zweite m von Dir ist richtig ( wenn man die Häufigkeit von eins mit beachtet) kleiner Fehler von mir.
Die Tabellen ( oder Zustände) sind nur für die Berechnung von einem einzigen Schritt korrekt. Das ist das blöde daran.
Bei sowas wird es dann interessant, und man muss jeden Schritt berechnen ... , m m r t f f f y m m x x x x
überleg .... ich glaub ich mach erstmal ein kleines Code Beispiel ... ich glaube nämlich, ich habs doch falsch erklärt, es gibt nämlich noch einen Schwellwert. Mit der Häufigkeit von 1 macht das nämlich keinen Sinn. .. Wieder die vielen Knoten im Gehirn ....

[marabu]

Wichtig ist, dass du den Algorithmus genau wiedergibst, sonst wird das nichts mit der Hilfe. Ich habe ihn mal mit meinem momentanen Kenntnisstand implementiert - Komplexität O(n).

marabu

[stoxx]

Zitat:

Zitat von marabu

Wichtig ist, dass du den Algorithmus genau wiedergibst
marabu

das hab ich jetz beim erstellen des Beispiels auch gemerkt. Also hier der Algorithmus mit Komplexitet n * (n-k)
O(n^2) ist das dann wohl ?

Ich habe mich in meinem Einführungsbeispiel vertan. Der Algorithmus ist aber eigentlich richtig beschrieben.
Es ist im Prinzip eine Bestimmung irgendeines Maxwertes zweimal hintereinander.

für mmrtfff kommt immernoch mmrtfff raus.
Interessant wird es erst, wenn man hinter diese Sequenz zum Beispiel anfängt den Buchstaben a anzufügen.

also z.B. mmrtfffaa

da kommmt raus. mmfffffaa



Hier der Quelltext, der sagt vielleicht mehr als tausend Worte.

Delphi-Quellcode:

type


TDatenMaxCount = record
  Buchstabe : Char;
  Count : Integer;
  StartIndex: Integer;
  MaxLen : Integer;
end;


TDatenSieger = record
  Buchstabe : Char;
  MaxLen: Integer;
end;


//==============================================================================

function ermittle(Sequenz : String)  : char;
var loop, charindex : Integer;
    CountArray : array[0..255] of Integer;
    Sieger : TDatenSieger;
    MaxCount : TDatenMaxCount;

begin

for loop := 0 to high(CountArray)  do
  CountArray[loop] := 0;


MaxCount.Buchstabe := Sequenz[1];
Maxcount.Count := 1;
MaxCount.StartIndex := 1;
MaxCount.MaxLen := 1;

Sieger.Buchstabe := MaxCount.Buchstabe;
Sieger.MaxLen := 1;



for loop := 2 to length(Sequenz) do
begin
   charindex :=  ord(Sequenz[loop]);
   inc(CountArray[charindex]);



   if charindex = ord(maxCount.Buchstabe)then
   begin
       inc(MaxCount.Count);
   end else
   begin
       // Eventuell Neuen Count Max bestimmen

       if CountArray[charindex] > MaxCount.Count then
       begin
          MaxCount.Count := CountArray[charindex];
          MaxCount.StartIndex := loop;
          MaxCount.Buchstabe := char(charIndex);
       end;

   end; // if else

   // wird solange erhöht, bis der nächste Maxcount an dessen stelle kommt
    MaxCount.MaxLen := loop - MaxCount.StartIndex;

   // Längen Maximum .. Sieger bestimmen
   // aktueller Maxcount kann den Sieger übertreffen

   if MaxCount.MaxLen > Sieger.MaxLen then
   begin
       Sieger.Buchstabe := MaxCount.Buchstabe;
       Sieger.MaxLen := MaxCount.MaxLen;

   end;


end;  // for

result := Sieger.Buchstabe;

end; // function ermittle

//==============================================================================

procedure TForm2.Button1Click(Sender: TObject);
var Eingabe, ausgabe, st : String;
    i, len : Integer;
begin


Eingabe := 'mmrtfff';
ausgabe := '';
len := length(Eingabe);


for i := 0 to len -1  do
begin
    st := copy(Eingabe, len -i, i+1);
    ausgabe := Ermittle(st) + ausgabe;
end; // for


showmessage(ausgabe);




end;  // buttonclick

[marabu]

Hallo.

Zitat:

Zitat von stoxx

Der Algorithmus ist aber eigentlich richtig beschrieben.

Dann stimmen die Beispielergebnisse aber nicht.

Code:

seq:   m  m  r  t  f  f  f
cnt:   1  2  1  1  1  2  3
rev:   2  1  1  1  3  2  1
rng:   6  4  3  2  3  2  1
res:   m  m  f  f  f  f  f

seq:   m  m  r  t  f  f  f  a  a
cnt:   1  2  1  1  1  2  3  1  2
rev:   2  1  1  1  3  2  1  2  1
rng:   6  4  3  2  5  4  2  2  1
res:   m  f  f  f  f  f  a  a  a

Habe eine Fassung meines Programms angehängt, welche die Kontrolltabellen ausgibt, wenn man einen Dateinamen als Aufrufparameter mitgibt. Die Verarbeitungsschleife wird mit einer leeren Sequenz abgebrochen.

Zitat:

Zitat von stoxx

Hier der Quelltext, der sagt vielleicht mehr als tausend Worte.

Die Redensart gilt nicht immer - nichtmal für jedes Bild.

Woher hast du eigentlich den Algortihmus? Gibt es eine authentische Beschreibung? Oder kannst du etwas über die zugrunde liegende Aufgabenstellung verraten?

Nachdenkliche Grüße vom marabu

[stoxx]

Zitat:

Dann stimmen die Beispielergebnisse aber nicht.

jaaa ... ;-) Maßgeblich ist der Quelltext, das soll rauskommen.
Mein Quelltext hab ich so gestaltet, dass man ihn gut debuggen kann und sieht was rauskommt, und mit welchen Werten er arbeitet.
Die Aufgabentellung ist kein Lehrbuchbeispiel, sondern eine Problem aus meiner eigenen Praxis.

Dein Beispiel ist da auch nicht richtig:

Zitat:

seq: m m r t f f f
cnt: 1 2 1 1 1 2 3
rev: 2 1 1 1 3 2 1
rng: 6 4 3 2 3 2 1
res: m m f f f f f

richtig ist: (also genau die gleiche Sequenz als ergebnis)

Zitat:

seq: m m r t f f f
res: m m r t f f f

als drittes Result kommt bei Dir f raus, stimmt aber nicht, da kommt ein r hin.
das deswegen.

das "r" errechnet sich aus aus r t f f f

(5 Buchstaben) .. das r hat bis einschließlich dem dritten Buchstaben die größte Häufigkeit (von eins) , bzw wird sie nicht durch eine andere Häufigkeit übertrofffen, erst mit dem 4 Buchstaben erlangt das F den obersten Rang. Da dann nur noch ein f danach kommt, ist die länge von r = 3 und f = 2 .. somit fällt die entscheidung für r

also m m r .. dann weiter ...

oder aber auch als neues Beisiel:

Zitat:

seq: m m r t f f f a
res: m m r f f f f a

[marabu]

Peinlich - ich habe ein Gleichheitszeichen vergessen:

Delphi-Quellcode:

// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    if (i = High(seq)) or (rng[i] >= maxRange) then  // muss natürlich >= sein !
// ...

Code:

seq:   m  m  r  t  f  f  f
cnt:   1  2  1  1  1  2  3
rev:   2  1  1  1  3  2  1
rng:   6  4  3  2  3  2  1
res:   m  m  r  f  f  f  f

Und immer noch O(n). Den Hintergrund magst du nicht aufdecken? Schade.

marabu