PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Möglichst lange Stringketten finden


nodh
2003-11-07, 22:29:54
Hallo!

Gegeben ist eine Textdatei, in der untereinander Wörter stehen. Das Programm soll daraus eine möglichst lange Kette bilden, die wie folgt aufgebaut sein muss:

ComputeRadfahreNordpoLaufeN....

Also das nächste Wort muss mit dem letzten Buchstaben des vorigen Wortes beginnen.

Wie könnt ich sowas elegant lösen?
Möglichst in Delphi...

ethrandil
2003-11-07, 23:03:23
Eine Möglichkeit, die mir spontan einfällt wäre:

Erstmal alle Wörter einlesen und nach Anfags und Endbuchstabe sortiert speichern.

Außerdem sollten die Wörter nach wortlänge sortiert sein.

Wenn du soweit bist, dann kannst du mit einem Buchstaben anfangen, nimmst das längste wort mit dem Anfangsbuchstaben. Dann das nächste mit dem Anfangsbuchstaben = Endbuchstabe des Vorherigen und so weiter.

Das wird nicht ganz optimal, aber effektiver als bruteforce, wenn es nicht hundertprozentig auf die längste Länge annkommt.

Eth

nodh
2003-11-07, 23:09:19
Es zählt nicht die Anzahl der Buchstaben, sondern die Anzahl der Wörter!

DocEW
2003-11-11, 17:07:40
Hi!

Interessante Frage... da ich momentan wenig Zeit habe, kann ich dir leider nur eine theoretische Antwort und keinen fertigen Algorithmus liefern:

Im Grunde mußt du einen Graphen untersuchen, dessen Knoten aus den Wörter bestehen, und bei dem eine Kante (v,w) genau dann vorhanden ist, wenn der letzte Buchstabe von v gleich dem ersten von w ist. In diesem Graphen suchst du den längsten existierenden Pfad. Das Blöde ist, daß der Graph Kreise hat ( "Auto <-> Oma" ), sonst könnte man eine Art "längster Weg"-Problem lösen. Kann man evtl. auch, wenn man irgendwie noch mit Knotenmarkierungen arbeitet ...

Mein Vorschlag, der auch etwas simpler ist, wäre von allen Knoten v_i eine Tiefensuche zu starten. So erhält man i spannende Bäume jeweils mit Wurzel v_i und einem tiefsten Blatt b. Die Knoten im Pfad (v_i,b) im Baum maximaler Tiefe sind dann deine Lösung.

Da die Tiefensuche bei n Knoten in O(n) läuft und du sie für alle Knoten ausführst müßte also noch eine O(n^2) Laufzeit drin sein. :-)

Was ich nicht ausgenutzt habe ist, daß Wörter die mit dem gleichen Buchstaben beginnen und/oder enden gewissermaßen austauschbar sind. Das könnte zu einer deutlichen Verringerung des Speicherbedarfs führen, für die Laufzeit bringt es glaube ich nix.

Ich hoffe das hilft entweder dir oder jemandem mit mehr Zeit als ich, der das für dich implementiert wenn du nichts damit anfangen kannst!

Ach ja, wenn dich die Implementation solcher Algorithmen allgemein interessiert, kann ich dir die Algorithmen-Bücher von Sedgewick empfehlen:
http://www.amazon.de/exec/obidos/search-handle-url/index=books-de&field-keywords=sedgewick&bq=1/ref=sr_aps_all/028-3673743-0906956

Viele Grüße,

DocEW

Xmas
2003-11-11, 17:14:23
Ich würde eher sagen, die Knoten des Graphen sind die Buchstaben, während die Wörter gerichtete Verbindungen sind.

ethrandil
2003-11-11, 17:20:49
Guck mal hier rein:
http://forum.java.sun.com/thread.jsp?forum=426&thread=370013&start=0&range=15&hilite=false&q=
Selbes Problem, andere Anwendung :)

Dort gibt es aber soweit ich gesehen hab keine endgültige Lösung.

Eth

DocEW
2003-11-11, 23:25:31
Original geschrieben von Xmas
Ich würde eher sagen, die Knoten des Graphen sind die Buchstaben, während die Wörter gerichtete Verbindungen sind.
Jo, haste Recht, das reicht auch und ist günstiger, da man dann nur 26 Knoten hat statt Anzahl der Wörter viele.

Haarmann
2003-11-11, 23:44:41
nodh

Kompliziertes Problem

Mit schwebt nur ein sinnvoller direkter Ansatz vor. Wörter die mit dem gleichen Buchstaben beginnen, wie enden, die fliegen mal raus, die kannste am Ende recht einfach noch separat berechnen.
Danach bestimmen, wieviele A,B, C,... etc Du hast Am Anfang und am Ende. Dann diese beiden Mengen (Anfang Ende) schneiden und die Schnittmenge ergibt die maximal mögliche Wörterzahl. Ob diese dann geht, musste zwar noch beweisen, aber das müsste imho die schnellste Variante darstellen, da Du wenigstens sinnvoll suchst und weisst, wo Du beginnst mit der Suche.

Obligaron
2003-11-12, 18:41:57
Narf, gerade auf "Alle Tabs schliessen" bei Mozilla gekommen, alles nochmal neu schreiben...

Dafür jetzt aber zügig ans Werk. Wörter werden erstmal vereinfacht dargestellt, ein Computer ist ein CR, da uns eh nur der Anfangs- und der Endbuchstabe intressieren. Und dies stellen wir nochmal anders dar, am besten in einer Struktur mit 26 Buchstaben und diese jeweils für alle 26 Buchstaben, also ingesammt 676 Kombinationen.
CR wird dann so abgespeichert C->R. Dazu wird ein counter angelegt, bzw. halt um eins hochgezählt. also C->R (1). Dies macht man dann mit allen Buchstabenkombinationen.
Als Beispiel nehme ich mal folgende Wörter her:
AB
BC
AB
BD
BE
CB
DC

Diese werden also alle in die oben angesprochen Form umgewandelt.
A->B (2)
B->C (1)
B->D (1)
B->E (1)
C->B (1)
D->C (1)

Dann fängt man bei A an und geht per Rekursion das ganze durch, dabei wird der Counter einer Verbinundg (z.b. A->B) immer runtergezählt. Einen Buchstaben darf man nur "aufrufen" wenn es noch ein Wort (also mindestens eine Verbindung, egal ob es danach weiter geht oder nicht) gibt. Wenn man dann mit A durch ist, macht man mit B weiter. Das solange bis man alle Buchstaben durch hat und dann sollte man auch den "längsten Weg" haben.

Ich hoff ich hab jetzt keinen Denkfehler drinnen.

MfG,
Obligaron

EDIT: Smilies ausgeschalten

ethrandil
2003-11-13, 06:52:37
So, dass hab ich gestern wg- serverschwäche nicht posten können...
:
Ja, der Ansatz ist nicht schlecht, aber du hast einen Denkfehler ;D

Wenn das aktuelle gerade ist A->B, dann muss das nächxte logischer weise B->* sein. Aber was wenn es nun mehrere Bs gibt? Dann nimmt man den ersten.
Aber was wenn man mit dem 2. weiter gekommen wäre?

Wenn schon Brute-Force denn schon ;-)

Wir haben eine Tabelle mit Wechselmöglichkeiten:
A->B
A->B
B->C
B->D
B->E
C->B
D->C

Dann hat man noch eine Struktur, die einen Ausgangswechsel und mehrere Folgetbäume ihrer eigenen Klasse hat.

Nun nimmt man mal einen Wechsel als Ausgangswechsel (A->B). Nun sucht man alle folgewechselmöglichkeiten (B->C, B->D, B->E). Von diesen erzeugt man wieder das selbe, jedoch entfernt man für sie alle bisherigen Wechsel aus den Wechselmöglichkeiten.
Man erhält eine Baumartige Struktur:


A->B
/ | \
B->C B->D B->E
| |
C->B D->C
/ \ |
B->D B->E C->B
| / \
D->C B->C B->E

(hoffe ich hab nichts vergessen)
So, das sind alle Möglichkeiten für Wortverkettungen mit dem Ausgangswort AB.
Nun muss man noch eine Rekursive Funktion schreiben, die die längste Kette findet!
etwas wie:

public Tauschkette getLongestChain(){
if( unterbäume.length == 0)
return new Tauschkette(null);

Tauschkette tmpLongest = null;
foreach(unterbäume as singleBaum){
Tauschkette tmpAct = singleBaum.getLongestChain();
if(tmpAct.length()+1 > tmpLongest.length()){
tmpLongest = new Tauschkette(singleBaum.ausgangsWort);
tmpLongest.hängAn(tmpAct);
}
}
return tmpLongest;
}


So, ..., wenn der aktuelle baum keinen unterwechsel hat, dann gib diesen zurück. Wenn nicht, dann prüfe welcher deiner Unterbäume die längste Verkettung zulässt. Dieser hänge ihn selber voran und gib ihn zurück...

Wieso ist es nur so kompliziert rekursionen zu erklären???

naja ... müsste so gehn.

(Die Sprache ist übrigens nur ein mix aus allem ;-) )

Obligaron
2003-11-13, 08:29:26
Original geschrieben von ethrandil
Ja, der Ansatz ist nicht schlecht, aber du hast einen Denkfehler ;D

Wenn das aktuelle gerade ist A->B, dann muss das nächxte logischer weise B->* sein. Aber was wenn es nun mehrere Bs gibt? Dann nimmt man den ersten.
Aber was wenn man mit dem 2. weiter gekommen wäre?

hmm ich hab gedacht das ist mit dem wort rekursion ausgiebig genug beschrieben. aufjedenfall soll er alle kombinationen duchprobieren, wenn er mit A anfängt. Dann macht man mit B als startbuchtsaben weiter usw. Also an sich habe ich das selbe gemeint wie du hier geschrieben hast, wohl bloss etwas schlecht beschrieben (währe nicht das erste mal *g*) ;).

Original geschrieben von ethrandil
Wenn schon Brute-Force denn schon ;-)

Also besser als reiner Brute-Force ist es schon :D

Original geschrieben von ethrandil

A->B
/ | \
B->C B->D B->E
| |
C->B D->C
/ \ |
B->D B->E C->B
| / \
D->C B->C B->E

(hoffe ich hab nichts vergessen)
So, das sind alle Möglichkeiten für Wortverkettungen mit dem Ausgangswort AB.
Nun muss man noch eine Rekursive Funktion schreiben, die die längste Kette findet!


Also für den Baum schreiben war ich mir zu faul, ich würds aber eh anders skitzieren.

Original geschrieben von ethrandil
Wieso ist es nur so kompliziert rekursionen zu erklären???

Also imho habe ich es garnicht erklärt ;).

Ich würd den Baum btw so machen:


(1)--C◄----(1)
| ▲ |
\ (1) |
▼ | |
A-(2)-►B-(1)-►D
|
(1)

E

Erster versuch startet dann mit A, läuft zu B (einzige möglichkeit), zählt den Counter A->B runter. Bei B hat man dann die auswahl zwischen C,D und E. Wir wählen C und machen dann weiter. von C gehts nach B und von B gehts nochmal nach D, dann ist sense, das währe unser erster weg den wir haben. Jetzt schauen wir ob es bei D noch einen anderen weg gegeben hätte => nein, also dann weiter zurück zu B, dort hätten wir noch nach E gehen können, also tun wir das => zweiter möglicher Weg. So testet man dann rekursiv alle Kombinationen durch. Also jetzt hoffe ich das wir das endlich haben ;).

MfG,
Obligaron

EDIT: btw muss man noch alle Anfangsbuchstaben einmal so durchprobieren, also einmal mit A starten, einmal mit B usw.

nodh
2003-11-15, 00:24:33
Danke erstmal für die vielen Antworten!

Werde sie mir mal genauer durchschauen!

@docEW:
Dein erstes Posting hilft mir leider gar nichts weiter, ich hab keine Ahnung wovon du redet :???: