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

[stoxx]

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  [color=#ff003f][size=18][b]F[/b][/size][/color]  f  f  f

das F ist falsch.

Das PRoblem ist, die Tabelle die Du verwendest, ist nur für den ersten Buchstaben gültig.
Die Fortgeschriebenen Häufigkeiten sind nur gültig, wenn man den ersten Buchstaben berechnen will.
Wenn man den zweiten Buchstaben berechnet, dann gelten ja andere fortgeschriebenen Häufigkeiten.
(Ob man bei meinem Algorithmus von vorn oder von hinten anfängt, ist egal)

in meinem Beispiel könnte man auch von vorn berechnen:

Delphi-Quellcode:

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

anstatt:

Delphi-Quellcode:

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

Das ist egal.


Ich dachte halt nur, wenn man von hinten anfängt, könnte man eventuell schon ergebnisse nutzen .. irgendwie .. vielleicht halt.
Also eventuell ..

[marabu]

Das von dir als falsch markierte f ergibt sich doch aus der Tatsache, dass der Bereich für das t in der Eingabesequenz an der betrachteten Stelle die Größe 2 hat (das erste f kann ), während das f als einzige relevante Alternative die Bereichsgröße 3 besitzt. Nach der Beschreibung deines Algorithmus qualifiziert der größere Bereich den "Sieger" - ergo wird das t vom f verdrängt. Hast du die Spielregeln geändert?

Außerdem kann ich deine Aussage zu meinen Hilfsvektoren cnt bzw. rev nicht nachvollziehen - vielleicht bin ich einfach schon zu müde. Auf jeden Fall nährt sich der Knobelcharakter deiner Aufgabe aus der individuellen Art, mit der du eine klare Formulierung des Algorithmus vermeidest. Vielleicht wird alles klarer, wenn du einmal die Bereichsgrößen darstellst. Stimmen denn die Angaben in meinem Vektor rng? Oder liegt da schon das Verständigungsproblem?

marabu

[stoxx]

Zitat:

Zitat von marabu

Das von dir als falsch markierte f ergibt sich doch aus der Tatsache, dass der Bereich für das t in der Eingabesequenz an der betrachteten Stelle die Größe 2 hat (das erste f kann ), während das f als einzige relevante Alternative die Bereichsgröße 3 besitzt. Nach der Beschreibung deines Algorithmus qualifiziert der größere Bereich den "Sieger" - ergo wird das t vom f verdrängt. Hast du die Spielregeln geändert?

Außerdem kann ich deine Aussage zu meinen Hilfsvektoren cnt bzw. rev nicht nachvollziehen - vielleicht bin ich einfach schon zu müde. Auf jeden Fall nährt sich der Knobelcharakter deiner Aufgabe aus der individuellen Art, mit der du eine klare Formulierung des Algorithmus vermeidest. Vielleicht wird alles klarer, wenn du einmal die Bereichsgrößen darstellst. Stimmen denn die Angaben in meinem Vektor rng? Oder liegt da schon das Verständigungsproblem?

marabu

das t wird vom f "noch" nicht verdrängt.

t wird von 4 bis 7 berechnet

t -> t ist einmal vorhanden, t hat Spannweite von 1
tf -> t ist einmal vorhanden, t hat Spannweite von 2
f ist einmal vorhanden, f hat Spannweite von 1

tff - f wird am häufigsten, Spannweite von 1 !! ab hier fängt die Zählung an für f (siehe Definition ganz oben)
t ist einmal vorhanden, Spannweite immer noch 2

tfff t hat immernoch die Spannweite von 2
f hat nun auch die Spannweite von 2 (ist aber noch nicht größer als die von t) .. daher ist der Sieger immer noch t

ich weiß, dass das Problem schwierig zu beschreiben ist. das sind Häufigkeitszählungen, aber das wird Dir nicht viel nützen.

Zitat:

Stimmen denn die Angaben in meinem Vektor rng?

Die Vektoren hab ich mir schon nicht mehr angeschaut, weil die fortlaufende Häufigkeitszählung falsch ist.
siehe das Beispiel. Weiß nicht so recht, was Dein Algo macht.
Denn die fortlaufenden Häufigkeit ist zur Berechnung des ersten Buchstaben eine andere, als wenn man den vierten Buchstaben berechnen würde.

Code:

seq:   f  m  m  r  t  f  f  f 
cnt:   1  1  2  1  1  [color=#ff003f][b]1 2 3 [/b][/color] 
rev:   1  2  1  1  1  3  2  1 
rng:   2  6  4  3  2  3  2  1 
res:   m  m  m  r  f  f  f  f

[x000x]

Moin moin,
ich habe auch mal versucht da durchzusteigen... Wie folgt habe ich
es verstanden:

Code:

___________________________________________________
1.
      _____4______
     |            |
 |f  m| m  r  t  f |f  f |          = x[0] = m (4)
 |____|            |_____|
   2                 2
___________________________________________________
2.
                       _1
                      |  |
  f |m  m  r  t  f  f |f           = x[1] = m (6)
    |_________________|
             6
___________________________________________________
3.
                    __2__
                   |     |
  f  m |m  r  t  f |f  f |         = x[2] = m (4)
       |___________|
             4
___________________________________________________
4.
                    __2__
                   |     |
  f  m  m |r  t  f |f  f |         = x[3] = r (3)
          |________|
              3
___________________________________________________
5.
                    __2__
                   |     |
  f  m  m  r |t  f |f  f |         = x[4] = t (da t >= f)
             |_____|
                2
___________________________________________________
6, 7 und 8.
 
  f  m  m  r  t |f  f  f |         = x[5..7] = f
                |________|
                     f
___________________________________________________
Ergebnis: m m m r t f f f

Sollte ich nicht daneben liegen, ergeben sich 2 Fragen:
1. Warum kommst du in deinem letzten Beitrag auf x[4] = f ?
2. Was ist mit dem Fall unter Punkt 1 bei einer Arraylänge n? Würden die F am ende
als neuer "Abschitt" gesehen werden?

Sollte ich daneben liegen... naja, ist halt schon spät :-)

[marabu]

Guten Morgen.

Zitat:

Zitat von stoxx

ab hier fängt die Zählung an für f

Erst durch diese Erklärung fällt mir auf, dass sich bei meiner Implementierung angrenzende Bereiche überlappen. Ich muss noch eine kleine Änderung an der abschließenden Berechnungsschleife einführen:

Delphi-Quellcode:

// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    maxRange := rng[i];
    maxSymbol := seq[i];
    for j := i + maxRange to High(seq) do
      if (j = i) or (rng[j] > maxRange) then
      begin
        maxSymbol := seq[j];
        maxRange := rng[j];
      end;
    Result[Succ(i)] := maxSymbol;
  end;
// ...

Die als falsch eingestuften "Häufigkeitszählungen" in meinem Programm sind übrigens gerade der Schlüssel zur Umstellung der Laufzeitkomplexität auf O(n).

Schönes Wochenende

marabu

[stoxx]

Hi x000x !

Deine Darstellung ist richtig ! :-) Danke !
Das hast Du komplett richtig verstanden, so soll es sein, weil die Darstellung so gut war, hab ich es mal für das Beispiel

a a b b c c a a gemacht.

Code:

1.
      
            
 |a  a  b  b  c  c  a  a |      = x[0] = a (8)
 |_______________________|
             8
___________________________________________________
2.               5
           ______________
          |              |
  a |a  b |b  c  c  a  a |      = x[1] = b (5)
    |_____|         
       2  
___________________________________________________
3.
      
            
  a  a |b  b  c  c  a  a |      = x[2] = b (6)
       |_________________|
                6
___________________________________________________
4.                    
                 ___3____                                  
                |        |                           
  a  a  b |b  c |c  a  a |      = x[3] = c (3)
          |_____|                                         
             2                                      
___________________________________________________
5.
                                                   
                                                   
  a  a  b  b |c  c  a  a |      = x[4] = c (4)
             |___________|                                      
                  4                                 
___________________________________________________
6.
                       _1_                            
                      |   |                          
  a  a  b  b  c |c  a |a  |     = x[5] = c (2)
                |_____|                                   
                   2                                
___________________________________________________

7.
                                                   
                                                   
  a  a  b  b  c  c |a  a |      = x[6] = a (2)
                   |_____|                                
                      2                             
___________________________________________________
2.
                                                   
                                                   
  a  a  b  b  c  c  a |a |      = x[7] = a (1)
                      |__|                             
                                                   
___________________________________________________
Ergebnis: a b b c c c a a

Deine Fragen:

Zitat:

1. Warum kommst du in deinem letzten Beitrag auf x[4] = f ?

Das ist ja das falsche Beispiel von marabu, Deins ist richtig.

Zitat:

2. Was ist mit dem Fall unter Punkt 1 bei einer Arraylänge n? Würden die F am ende
als neuer "Abschitt" gesehen werden?

zu einer Länge von n kommen wir ja, wenn wir weitere Elemente anfügen. Bei jedem neuen Element muss die gesamte Berechnung neu durchgeführt werden.
Oder aber eben irgendeine intelligente andere Lösung ...

Hi Marabu,

Mit Deinem Code kommt bei a a b b c c a a als falsches Ergebnis: a c b b c c a a raus, ist das jetzt nur noch ein kleiner Fehler oder stimmt die Logik nicht ?

Danke an Euch !

[marabu]

Hallo stoxx,

Zitat:

Mit Deinem Code kommt bei a a b b c c a a als falsches Ergebnis: a c b b c c a a raus, ist das jetzt nur noch ein kleiner Fehler oder stimmt die Logik nicht ?

bist du sicher, dass dein Ergebnis stimmt? Meine Interpretation deiner Regeln ergibt etwas anderes:

Code:

___________________________________________________
4.                   
                 __2__                                 
                |     |                           
  a  a  b |b  c |c  a |a |      = x[3] = b (2) (da b >= c)
          |_____|     |__|                                    
             2          1                           
___________________________________________________

marabu

PS: Kompliment von mir an x000x für die gelungene Semigrafik.

[stoxx]

Hi Marabu,

das Ergebnis stimmt, denn bei der x[3] Berechnung (seit x000x beginnt die Zählung bei Null, achtung !) wird: b c c a a herangezogen und da kommt "c" zweimal drin vor.
Da kein anderer Buchstabe bis zum Ende dreimal vorkommt, bleibt c der Sieger bis zum Schluß. Das meinte ich ja damit, dass die Häufigkeitszählungen immer neu gemacht werden müssen.

Zitat:

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.

[marabu]

Hi stoxx,

Zitat:

Zitat von stoxx

das Ergebnis stimmt, denn bei der x[3] Berechnung (seit x000x beginnt die Zählung bei Null, achtung !) wird: b c c a a herangezogen und da kommt "c" zweimal drin vor.

ich halte mich lieber an die Beschreibung des Algorithmus, die du zitierst und hoffe, dass da kein Fehler drin ist. Darin steht, dass die Dimensionierung des Bereiches eines Buchstaben diesen für die Besetzung der Stelle qualifiziert. Die Häufigkeit eines Buchstaben dient nur zur Abgrenzung der Bereiche und nicht als Kriterium für den "Sieger".

Häufigkeit - nach meiner Auffassung ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt. Leider ist diese Definition so nicht aus der Beschreibung des Algorithmus zu entnehmen. Ein Testfall wäre die Sequenz aabcaccc.

Allerdings zeigt mir dein Beispiel mit der Sequenz aabbccaa, dass ich die Bereichsüberlappung noch nicht ganz ausgeschaltet habe. Das falsche c auf der zweiten Stelle eliminiere ich durch folgende Korrektur:

Delphi-Quellcode:

// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    maxRange := rng[i];
    maxSymbol := seq[i];
    j := i + maxRange;
    while j <= High(seq) do
    begin
      if (j = i) or (rng[j] > maxRange) then
      begin
        maxSymbol := seq[j];
        maxRange := rng[j];
      end;
      Inc(j, rng[j]);  // hic salta
    end;
    Result[Succ(i)] := maxSymbol;
  end;
// ...

Wegen der Sprünge habe ich die FOR Schleife durch eine WHILE Schleife ersetzt.

Zitat:

Zitat von stoxx

Da kein anderer Buchstabe bis zum Ende dreimal vorkommt, bleibt c der Sieger bis zum Schluß.

Steht das nicht im Widerspruch zu dem hier:

Code:

___________________________________________________
5.
                    __2__
                   |     |
  f  m  m  r |t  f |f  f |         = x[4] = t (da t >= f)
             |_____|
                2
___________________________________________________

marabu

[stoxx]

Zitat:

Die Häufigkeit eines Buchstaben dient nur zur Abgrenzung der Bereiche und nicht als Kriterium für den "Sieger".

richtig

Zitat:

Häufigkeit - nach meiner Auffassung ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt.

mit Häufigkeit ist die Anzahl der Vorkommen eines Buchstaben gemeints.

Zitat:

ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt

ähm, nochmal, versteh ich nicht ..

Zitat:

eliminiere ich durch folgende Korrektur:

aber es funktioniert doch immernoch nicht
Ich mach Dir ungern Vorschriften, da Du Dir die Mühe gemacht hast und Dir wirklich mal Quellcode überlegt hast.
Dafür bin ich Dir unheimlich dankbar.
Deswegen sorry, aber warum nimmst Du nicht einfach mal meinen Quelltext, kompiliest ihn und schaust ob Dein Programm dasselbe rechnet.
Das tut es nämlich nicht.
für aabbccaa kommt bei Dir jetzt auch aabbccaa raus ... jetzt ist noch ein richtig grober fehler drin.
Denke aber immernoch, dass Du das Problem anders verstanden hast, als ich wollte.
Wo siehst Du in dem Beispiel ein Widerspruch ?

für die Berechnung ist relevant

tfff

und da ist t über einen Bereich von 2 gültig;
und f über einen Bereich von 2.
Da aber f noch nicht über einen Bereich von 3 Gültigkeit hatte, somit ist t noch der Sieger.
hmmmmm .. fragend anschau ...
(richtigerweise müsste die Begründung aber heißen, da f <= t )

Code:

5.
                    __2__
                   |     |
  f  m  m  r |[color=#ff003f]t[/color]  f |f  f |         = x[4] = t (da t >= f)
             |_____|
                2
___________________________________________________

[marabu]

Hi stoxx,

dein erstes Beispiel hatte einen Fehler - du erinnerst dich? Die Beschreibung des Algorithmus ist nicht vollständig - der Begriff Häufigkeit ist nicht ausreichend definiert. Mir fehlen zuverlässige Testfälle zur Verifikation einer Implementierung. Als Referenz bietest du mir deinen Code an. Ich habe ihn analysiert und musste als erstes festgestellen, dass du jeweils den ersten Buchstaben eines Abschnittes nicht in die Häufigkeitszählung (CountArray) einfließen lässt. Interessanterweise hat das bei mehreren Testsequenzen keinen Einfluss auf das Ergebnis, aber es erschüttert auch mein Vertrauen in deinen Referenzcode.

Eines ist mir inzwischen klar - mein ursprüngliches Problemverständnis ist falsch, da ich die lückenhaften Informationen durch Fehlinterpretation geschlossen habe. Damit ist auch mein Code unbrauchbar, obwohl er gelegentlich richtige Eregbnisse gebracht hatte. Häufigkeiten waren in meinem Code homogene Teilkettenlängen. In deiner Implementierung interessieren keine statischen Häufigkeiten, weder die Häufigkeit in der Eingabesequenz, noch die Häufigkeit im untersuchten Abschnitt. Du arbeitest mit einer dynamischen Häufigkeit im Abschnitt. (Sequenz nenne ich hier die ursprüngliche Eingabe, Abschnitt die iterativ um eine Stelle gekürzte Sequenz.)

Ich hatte schon sehr früh auf die Bedeutung einer vollständigen und korrekten Beschreibung für den Algorithmus hingewiesen. Der von dir zitierte Text scheint nur ein Fragment deiner Aufgabenstellung zu sein. Aus Gründen die ich nur ahnen kann, scheust du die Preisgabe von Hintergrundinformationen.

Wenn die dynamische Berechnung der Häufigkeit in deinem Code korrekt ist, dann wirst du wohl prinzipiell von O(n*n) nicht wegkommen. Eine Voraussetzung für die Reduktion der Komplexität wäre eine feste Intervallgrenze (eine genügt), aber was ich hier mit dynamischer Berechnung bezeichne, basiert auf einem sliding window - da ist keine Vorberechnung der Häufigkeiten sinnvoll.

Freundliche Grüße vom marabu

[stoxx]

Hi Marabu,

naja .. dann werde ich es wohl bei dem schlechten Laufzeitverhalten belassen müssen. Hatte gehofft, dass es vielleicht eine Abkürzung gäbe.

Delphi-Quellcode:

Als Referenz bietest du mir deinen Code an. Ich habe ihn analysiert und musste als erstes festgestellen, dass du jeweils den ersten Buchstaben eines Abschnittes nicht in die Häufigkeitszählung (CountArray) einfließen lässt.

Da hast Du doch glatt noch einen kleinen Bug entdeckt. hehe .. aber das liegt einfach dran, dass ich beim Initialisieren des ersten Buchstabens das doch glatt vergessen habe.
Der erste Buchstabe wird aber bei ganz langen Zeichenketten sowieso uninteressant .. daher hab ich wohl etwas geschludert ;-)
NAja .. hab vielen Dank für Deine Bemühungen, das Problem zu kapieren, war nicht einfach ...