LebensnebeL

Übersicht

Sonstiges

Smalltalk

	Splinner Betreff: LebensnebeL	Fr, Jun 04, 2010 0:02 Antworten mit Zitat
hi leute... hab da ne interessante idee... würde gerne ein programm schreiben welches aus einer liste aller vorhandenen deutschen wörter jedes wort ,welches rückwärts geschrieben noch sinn ergibt , herausfiltert und in einer anderen liste speichert. d.h.: jedes wort aus der liste muesste umgedreht und verglichen werden.gibt es eine uebereinstimmung soll es rausgeschrieben werden. klingt erstmal nicht besonders schwer was.. aber hab mich gerade nach 6 jahren ohne programmieren mal wieder ran gesetzt und muss festellen das ich fast alles vergessen habe.. ich hoff ich hab jemandem nen guten anspurn gegeben... bis gleich

Splinner

Betreff: LebensnebeL

Fr, Jun 04, 2010 0:02
Antworten mit Zitat

hi leute...

hab da ne interessante idee...
würde gerne ein programm schreiben welches aus einer liste aller vorhandenen deutschen wörter jedes wort ,welches rückwärts geschrieben noch sinn ergibt , herausfiltert und in einer anderen liste speichert.
d.h.: jedes wort aus der liste muesste umgedreht und verglichen werden.gibt es eine uebereinstimmung soll es rausgeschrieben werden.
klingt erstmal nicht besonders schwer was..
aber hab mich gerade nach 6 jahren ohne programmieren mal wieder ran gesetzt und muss festellen das ich fast alles vergessen habe..
ich hoff ich hab jemandem nen guten anspurn gegeben...

bis gleich

	Xeres Moderator	Fr, Jun 04, 2010 0:12 Antworten mit Zitat
Und? In welcher (programmier)Sprache? Wenn man ein Wörterbuch/Liste besitzt ist die Aufgabe in wenigen Zeilen erledigt. Ich glaub aber nicht, dass du mehr als Palindrome erhältst. Edit: Du suchst definitiv nur Palindrome - das wird vielleicht schwer, da ich nicht glaube, dass z.B. "LebensnebeL" in einem Wörterbuch zu finden ist. Edit: Es ist spät (und lesen und verstehen hapert schon offensichtlich), drum meine letzte Empfehlung: left, right, mid.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Fr, Jun 04, 2010 0:12
Antworten mit Zitat

Und? In welcher (programmier)Sprache?
Wenn man ein Wörterbuch/Liste besitzt ist die Aufgabe in wenigen Zeilen erledigt. Ich glaub aber nicht, dass du mehr als Palindrome erhältst.

Edit: Du suchst definitiv nur Palindrome - das wird vielleicht schwer, da ich nicht glaube, dass z.B. "LebensnebeL" in einem Wörterbuch zu finden ist.

Edit: Es ist spät (und lesen und verstehen hapert schon offensichtlich), drum meine letzte Empfehlung:
left

, right

, mid

Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	Splinner	Fr, Jun 04, 2010 0:27 Antworten mit Zitat
jo stimmt.. ich bin auch gerade auf palindrome gestossen.. da gibt es schon jede menge listen.. natuerlich das mit dem woerterbuch- das stimmt auch ,das lebensnebel warscheinlich nicht drin steht. hm... naja waer schon witzig..trotzdem

Splinner

Fr, Jun 04, 2010 0:27
Antworten mit Zitat

jo stimmt..
ich bin auch gerade auf palindrome gestossen..
da gibt es schon jede menge listen..

natuerlich das mit dem woerterbuch- das stimmt auch ,das lebensnebel warscheinlich nicht drin steht.

hm...
naja waer schon witzig..trotzdem

	ZaP	Fr, Jun 04, 2010 12:13 Antworten mit Zitat
Ich denke, Du wirst nicht drumrum kommen, die Wörter selbst zu generieren, oder direkt aus dem Wörterbuch zu nehmen, und mit dem Wörterbuch zu vergleichen. Dabei würde ich immer die linke Hälfte nehmen, die rechte Hälfte erzeugen, und die auch abgleichen. Wäre interessant, wie lange so ein Programm läuft.
Starfare: Worklog, Website (download)

ZaP

Fr, Jun 04, 2010 12:13
Antworten mit Zitat

Ich denke, Du wirst nicht drumrum kommen, die Wörter selbst zu generieren, oder direkt aus dem Wörterbuch zu nehmen, und mit dem Wörterbuch zu vergleichen.
Dabei würde ich immer die linke Hälfte nehmen, die rechte Hälfte erzeugen, und die auch abgleichen. Wäre interessant, wie lange so ein Programm läuft.

Starfare: Worklog, Website (download)

	Pummelie	Fr, Jun 04, 2010 13:40 Antworten mit Zitat
Du solltest mit Types arbeiten, und die Wörterbuchliste in eines einlesen.
It's done when it's done.

Pummelie

Fr, Jun 04, 2010 13:40
Antworten mit Zitat

Du solltest mit Type

s arbeiten, und die Wörterbuchliste in eines einlesen.

It's done when it's done.

	Thunder	Fr, Jun 04, 2010 14:29 Antworten mit Zitat
Nur so nebenbei: Ich glaube, dass es bei einer größeren Menge an Worten nicht mehr (mit BB) sinnvoll ist, da es einfach zu lange brauchen würde (Types sind dynamisch - benötigen eine Zeit zum initialisieren, adden von neuen Werten, löschen von alten...), dazu kommt, dass BB nicht unbedingt eine schnelle Sprache ist; besonders, wenn man nicht über einen Computer mit höherer Leistung verfügt.
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Thunder

Fr, Jun 04, 2010 14:29
Antworten mit Zitat

Nur so nebenbei: Ich glaube, dass es bei einer größeren Menge an Worten nicht mehr (mit BB) sinnvoll ist, da es einfach zu lange brauchen würde (Types sind dynamisch - benötigen eine Zeit zum initialisieren, adden von neuen Werten, löschen von alten...), dazu kommt, dass BB nicht unbedingt eine schnelle Sprache ist; besonders, wenn man nicht über einen Computer mit höherer Leistung verfügt.

Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

	Silver_Knee	Fr, Jun 04, 2010 19:15 Antworten mit Zitat
wenn du die länge der liste hast. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Dim wort$(laenge) ;..einlesen Readline bla ;2. file=WriteFile For count=0 To laenge-1 For countcount=laenge-1 To count Step -1 If vergleicherueckwaerts(wort(count),wort(countcount)) WriteLine(file,wort(count)) EndIf Next Next func vergleicherueckwaerts(s1$,s2$) If Len(s1)=Len(s2) For count=1 To Len(s1) If Mid(s1,count,1)<>Mid(s2,Len(s1)-count,1) Next Else Return False EndIf Return True End func ungetestet... kann sein dass irnwo n +1 oder n -1 fehlt gib dir am besten mit debuglog alle count und len-count aus. Ich weiß man gibt normalerweise net gleich code aber ich hat grad lust den zu schreiben.

Silver_Knee

Fr, Jun 04, 2010 19:15
Antworten mit Zitat

wenn du die länge der liste hast.
BlitzBasic: [AUSKLAPPEN]

Dim wort$(laenge)
;..einlesen Readline bla
;2. file=WriteFile

For count=0 To laenge-1
  For countcount=laenge-1 To count Step -1
    If vergleicherueckwaerts(wort(count),wort(countcount))
      WriteLine(file,wort(count))
    EndIf
  Next
Next

func vergleicherueckwaerts(s1$,s2$)
  If Len(s1)=Len(s2)
    For count=1 To Len(s1)
      If Mid(s1,count,1)<>Mid(s2,Len(s1)-count,1)
    Next
  Else
    Return False
  EndIf
  Return True
End func

ungetestet... kann sein dass irnwo n +1 oder n -1 fehlt gib dir am besten mit debuglog alle count und len-count aus.

Ich weiß man gibt normalerweise net gleich code aber ich hat grad lust den zu schreiben.

	Midimaster	Fr, Jun 04, 2010 20:24 Antworten mit Zitat
Also so kostet es aber sehr viel Zeit! Drei Tipps: 1. Wäre doch besser, wenn man das Ausgangswort erstmal umdreht und dann diesen String im Wörterbuch vergleicht. 2. Außerdem wäre es sinnvoll, das Wörterbuch alphabetisch vorzusortieren. Dann braucht man nur einen Teil des Wörterbuchs zu checken. 3. Oder gar interativ gezielt das ähnlichste Wort im vorsortierten Wörterbuch zu fischen. So kommt man bei 1.000.000 Wörter (= ca. 2 hoch 20) auf nur max 20 Versuche, bis das ähnlichste Wort gefunden ist. 4. Ein wenig abgefahren, aber.... Beispiel: "WINDELN" z.b. sieht rückwärts so aus: "NLEDNIW". "MARSCH" sieht so aus "HCSRAM" Da könnte man ja eine Selectionsstufe vorschalten die Wörter mit unsinnigen Wortanfängen gleich herausnimmt. mit "NL" beginnen einfach keine Wörter an im Deutschen. Eine Tabelle mit den denkbaren 27*27 Doppelbuchstaben-Kombis "AA bis "ZZ" würde sicherlich dafür sorgen, dass gut 2/3 der Wörter schon vor dem Vergleich rausfliegt.

Midimaster

Fr, Jun 04, 2010 20:24
Antworten mit Zitat

Also so kostet es aber sehr viel Zeit!

Drei Tipps:
1.
Wäre doch besser, wenn man das Ausgangswort erstmal umdreht und dann diesen String im Wörterbuch vergleicht.

2.
Außerdem wäre es sinnvoll, das Wörterbuch alphabetisch vorzusortieren. Dann braucht man nur einen Teil des Wörterbuchs zu checken.

3.
Oder gar interativ gezielt das ähnlichste Wort im vorsortierten Wörterbuch zu fischen. So kommt man bei 1.000.000 Wörter (= ca. 2 hoch 20) auf nur max 20 Versuche, bis das ähnlichste Wort gefunden ist.

4.
Ein wenig abgefahren, aber....
Beispiel: "WINDELN" z.b. sieht rückwärts so aus: "NLEDNIW". "MARSCH" sieht so aus "HCSRAM" Da könnte man ja eine Selectionsstufe vorschalten die Wörter mit unsinnigen Wortanfängen gleich herausnimmt. mit "NL" beginnen einfach keine Wörter an im Deutschen. Eine Tabelle mit den denkbaren 27*27 Doppelbuchstaben-Kombis "AA bis "ZZ" würde sicherlich dafür sorgen, dass gut 2/3 der Wörter schon vor dem Vergleich rausfliegt.

	BBPro2	Sa, Jun 05, 2010 11:57 Antworten mit Zitat
wieso sollte man ausschließlich palindrome erhalten ? hab jetzt zwar kein gegebeispiel gefunden, aber ich bezweifle, dass es kein einziges nicht palindrom gibt, welches die eigenschaft erfüllt im übrigen fürchte ich, dass das ganze NP-Vollständig ist und somit exponentielle laufzeit hat was bei größeren wörterbüchern zu laufzeiten im jahrtausend bereich führen könnte^^ oder fällt einem ein schnellerer algorithmus ein ? klar das umdrehen muss jeweils nur einmal geschehen, aber der vergleich müsste exponentiell sein oder?

BBPro2

Sa, Jun 05, 2010 11:57
Antworten mit Zitat

wieso sollte man ausschließlich palindrome erhalten ?
hab jetzt zwar kein gegebeispiel gefunden, aber ich bezweifle, dass es
kein einziges nicht palindrom gibt, welches die eigenschaft erfüllt

im übrigen fürchte ich, dass das ganze NP-Vollständig ist und somit exponentielle
laufzeit hat was bei größeren wörterbüchern zu laufzeiten im jahrtausend bereich führen könnte^^

oder fällt einem ein schnellerer algorithmus ein ?
klar das umdrehen muss jeweils nur einmal geschehen, aber der vergleich müsste
exponentiell sein oder?

	Xeres Moderator	Sa, Jun 05, 2010 13:20 Antworten mit Zitat
Die Frage, ob ein Wort rückwärts geschrieben noch "Sinn" ergibt ist unlösbar. Zum einen ist Sinn immer Subjektiv und damit von einem Programm so gut wie nicht erkennen, und die einzige Möglichkeit es zu erkennen, bestünde darin, alle sinnigen(!) Wortkompositionen zu vergleichen. Das bedeutet nichts anderes, als dass das Programm eine Wörterliste braucht, die bereits das Ergebnis enthält.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Sa, Jun 05, 2010 13:20
Antworten mit Zitat

Die Frage, ob ein Wort rückwärts geschrieben noch "Sinn" ergibt ist unlösbar. Zum einen ist Sinn immer Subjektiv und damit von einem Programm so gut wie nicht erkennen, und die einzige Möglichkeit es zu erkennen, bestünde darin, alle sinnigen(!) Wortkompositionen zu vergleichen. Das bedeutet nichts anderes, als dass das Programm eine Wörterliste braucht, die bereits das Ergebnis enthält.

	BBPro2	Sa, Jun 05, 2010 15:35 Antworten mit Zitat
@xeres: was man braucht ist eine komplette liste von wörtern (-> duden) dann dreht man das erste wort um und vergleicht es mit allen wörtern aus dem duden. ist es enthalten macht es "sinn" ist es nicht enthalten macht es keinen sinn. problem ist hierbei wie gesagt die laufzeit welche exponentiell ist und damit keinen in unserem leben terminierenden algorithmus liefert. aber unlösbar ist das problem sicherlich nicht... und wieso enthält die wörterliste bereits das ergebnis? das ist nicht richtig

BBPro2

Sa, Jun 05, 2010 15:35
Antworten mit Zitat

@xeres:

was man braucht ist eine komplette liste von wörtern (-> duden)
dann dreht man das erste wort um und vergleicht es mit allen wörtern aus dem
duden. ist es enthalten macht es "sinn"
ist es nicht enthalten macht es keinen sinn.

problem ist hierbei wie gesagt die laufzeit welche exponentiell ist und damit
keinen in unserem leben terminierenden algorithmus liefert.

aber unlösbar ist das problem sicherlich nicht...

und wieso enthält die wörterliste bereits das ergebnis? das ist nicht richtig

	BladeRunner Moderator	Sa, Jun 05, 2010 15:38 Antworten mit Zitat
Lebensnebel. Hier würde eine simple Wortsuche schon versagen.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Sa, Jun 05, 2010 15:38
Antworten mit Zitat

Lebensnebel.
Hier würde eine simple Wortsuche schon versagen.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	mpmxyz	Sa, Jun 05, 2010 15:48 Antworten mit Zitat
Exponentielle Laufzeit? Da rechne ich mal nach! Code: [AUSKLAPPEN] [EINKLAPPEN] gegeben: n nach Duden sortierte Wörter Jedes Wort durchgehen lineare Abhängigkeit -> n Das Wort umdrehen fast konstant, wenn man die Abhängigkeit von der Wörterzahl betrachtet -> 1 nach dem umgedrehten Wort suchen logarithmisch bei binärer Suche, n bei "dummer" Suche ->log(n) oder n ein Vergleich zweier Wörter auch fast konstant, wenn man die Abhängigkeit von der Wörterzahl betrachtet -> 1 Wenn man jetzt nach bestimmten Regeln rechnet kommt man auf diese beiten Laufzeitformeln: O(n)=n*log(n) mit binärer Suche - verdoppeln von n -> etwas mehr als eine Verdopplung der Laufzeit O(n)=n² mit der "dummen" Suche - verdoppeln von n -> vervierfachen der Zeit mfG mpmxyz
Moin Moin! Projekte: DBPC CodeCruncher Mandelbrot-Renderer

mpmxyz

Sa, Jun 05, 2010 15:48
Antworten mit Zitat

Exponentielle Laufzeit? Da rechne ich mal nach! Wink

Code: [AUSKLAPPEN]

gegeben: n nach Duden sortierte Wörter
Jedes Wort durchgehen
lineare Abhängigkeit -> n
Das Wort umdrehen
fast konstant, wenn man die Abhängigkeit von der Wörterzahl betrachtet -> 1
nach dem umgedrehten Wort suchen
logarithmisch bei binärer Suche, n bei "dummer" Suche ->log(n) oder n
ein Vergleich zweier Wörter
auch fast konstant, wenn man die Abhängigkeit von der Wörterzahl betrachtet -> 1

Wenn man jetzt nach bestimmten Regeln rechnet kommt man auf diese beiten Laufzeitformeln:
O(n)=n*log(n) mit binärer Suche - verdoppeln von n -> etwas mehr als eine Verdopplung der Laufzeit
O(n)=n² mit der "dummen" Suche - verdoppeln von n -> vervierfachen der Zeit

mfG
mpmxyz

Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

	Xeres Moderator	Sa, Jun 05, 2010 15:49 Antworten mit Zitat
Natürlich, wenn du den Sinn so definierst, funktioniert das bei bekannten Wörtern. Das Beispiel "LebensnebeL" ist aber gerade eine Komposition, und müsste als solche mit allen anderen möglichen Kompositionen aus dem Wörtbuch verglichen werden... Bei einer kompletten Liste kann man viel optimieren, Midimaster hat ja Stichworte geliefert. Das geht ratzfatz.
Win10 Prof.(x64)/Ubuntu 16.04\|CPU 4x3Ghz (Intel i5-4590S)\|RAM 8 GB\|GeForce GTX 960 Wie man Fragen richtig stellt \|\| "Es geht nicht" \|\| Video-Tutorial: Sinus & Cosinus THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Sa, Jun 05, 2010 15:49
Antworten mit Zitat

Natürlich, wenn du den Sinn so definierst, funktioniert das bei bekannten Wörtern.
Das Beispiel "LebensnebeL" ist aber gerade eine Komposition, und müsste als solche mit allen anderen möglichen Kompositionen aus dem Wörtbuch verglichen werden...
Bei einer kompletten Liste kann man viel optimieren, Midimaster hat ja Stichworte geliefert. Das geht ratzfatz.

	BBPro2	Sa, Jun 05, 2010 15:51 Antworten mit Zitat
ich hab vergessen dass die ergebnisse bereits bestehen und alphabetisch sortiert sein können hab nen kater von gestern bin davon ausgegangen dass man das umgedrehte wort mit jedem möglichen lösungswort abgleichen muss ^^

BBPro2

Sa, Jun 05, 2010 15:51
Antworten mit Zitat

ich hab vergessen dass die ergebnisse bereits bestehen und alphabetisch sortiert sein können

hab nen kater von gestern Wink

bin davon ausgegangen dass man das umgedrehte wort mit jedem möglichen lösungswort
abgleichen muss ^^

Übersicht

Sonstiges

Smalltalk

Nach Oben

BlitzBasic Portal

LebensnebeL

Betreff: LebensnebeL