Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » minimale Anzahl an Operationen, um ein Palindrom zu erhalten
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule minimale Anzahl an Operationen, um ein Palindrom zu erhalten
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-15


Hallo,

Gegeben ist ein Eingabe String. Nun soll die minimale Anzahl an Operationen (Zeichen einfügen, Zeichen löschen, Zeichen ändern), die den String in ein Palindrom verwandeln, ausgegeben werden.

Ich habe das ganze mit dynamischer Programmierung gelöst, es ähnelt dem klassischen Levensthein Problem, allerdings können die Strings bis zu 1000 Zeichen groß sein und ein zweidimensionales Array ist dafür zu langsam. Hat jemand eine Idee, wie man es ohne zweidimensionales Array und dabei schneller lösen kann?
Danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-15


Anstatt das volle Quadrat zu betrachten, könntest Du Dich auf einen beschränkten Bereich um die Diagonale konzentrieren.
Inhaltlich entspräche das der Vorgabe, dass man in der einen "Hälfte" des Strings nicht deutlich mehr Zeichen löschen (bzw. einfügen) darf als in der anderen Hälfte. Natürlich lassen sich Beispiel konstruieren, bei denen die optimale Lösung dann nicht mehr gefunden wird, im Allgemeinen sollte man aber zu brauchbaren Ergebnissen kommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-17


Das hilft mir leider nicht sonderlich, aber danke für deine Antwort!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-05-18


Analog zum Levenshtein-Problem kann man vermutlich auf das zweidimensionale Array verzichten.

Asymptotisch bliebe die Laufzeit damit jedoch quadratisch.

Andererseits sollte das für Strings der Länge 1000 Zeichen kein Problem sein. (wenige Millisekunden Laufzeit auf normalen Plattformen)


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-05-19


Ich habe es mal in Java implementiert.
Algorithmus ist von StackOverflow.
Diagonalwerte oder deren Nachbarn aus der Levenshteindistanzmatrix zwischen Wort und dessen Umkehrung ergeben die minimale Palindromdistanz.


Implementierung mit voller Matrix:

palindromDistance(abc) = 1
palindromDistance(abcdcdcbb) = 1
palindromDistance(abcd) = 2
palindromDistance(mohammadsajjadhossain) = 8 // Stackoverflow Testcase
palindromDistance(randomWordOfLength=10) in 0ms.
palindromDistance(randomWordOfLength=20) in 0ms.
palindromDistance(randomWordOfLength=100) in 3ms.
palindromDistance(randomWordOfLength=1000) in 36ms.
palindromDistance(randomWordOfLength=2000) in 72ms.
palindromDistance(randomWordOfLength=5000) in 623ms.
palindromDistance(randomWordOfLength=10000) in 4379ms.



Speichereffiziente Zwei-Reihen-Variante:

efficientDistance(abc) = 1
efficientDistance(abcdcdcbb) = 1
efficientDistance(abcd) = 2
efficientDistance(mohammadsajjadhossain) = 8
efficientDistance(randomWordOfLength=10) in 0ms.
efficientDistance(randomWordOfLength=20) in 0ms.
efficientDistance(randomWordOfLength=100) in 3ms.
efficientDistance(randomWordOfLength=1000) in 33ms.
efficientDistance(randomWordOfLength=2000) in 44ms.
efficientDistance(randomWordOfLength=5000) in 195ms.
efficientDistance(randomWordOfLength=10000) in 822ms.
efficientDistance(randomWordOfLength=20000) in 3287ms.
efficientDistance(randomWordOfLength=50000) in 20188ms.
efficientDistance(randomWordOfLength=100000) in 73963ms.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-19


Danke für deine Mühe, ich habe den Post auch gelesen :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2021-05-19


2021-05-17 16:41 - dvdlly in Beitrag No. 2 schreibt:
Das hilft mir leider nicht sonderlich, aber danke für deine Antwort!

Vielleicht könntest Du ja erläutern, warum Dir das nicht hilft. Worin Dein Problem besteht, ist (mir) noch nicht klar geworden. Sind Dir 0,03 Sekunden zu lang?

[Die Antwort wurde nach Beitrag No.4 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-19


Tut mir Leid, das hätte ich an der Stelle wohl erwähnen sollen.
Das Problem ist, dass als Eingabe auch eher konstruierte Strings vorkommen, so dass man mit diesem Vorgehen nicht die minimale Anzahl an Operationen ausgibt - so wie du es beschrieben hast. Allerdings ist es zwingend notwendig, dass der Algorithmus korrekt ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2867
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-05-19


Der Algorithmus von Stackoverflow IST korrekt.
Er liefert immer die minimale Editierdistanz in quadratischer Worst-Case-Laufzeit.


Edit:
Poste doch einfach mal deine Implementierung und Testcases.
Dann können wir Ergebnisse und Laufzeiten vergleichen.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-19


Ich habe mich auf das von Kitaktus vorgeschlagene Verfahren bezogen. Ich bin davon ausgegangen, dass er mit dem Einwand "...natürlich lassen sich Beispiele konstruieren, bei denen die optimale Lösung nicht gefunden wird..." Recht hat. Falls er eigentlich den gleichen Algorithmus wie SO meinte, dann hast du natürlich Recht.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2021-05-19


Eine exakte Lösung ohne quadratische Laufzeit ist wohl nicht möglich. Wenn Du also schreibst: "Mein Algorithmus hat quadratische Laufzeit, das ist mir aber zu langsam." dann gibt es mehrer Interpretationen, dafür was Du eigentlich willst:
a) einen deutlich schnelleren aber nicht exakten Algorithmus
b) einen exakten Algorithmus mit besserem asymptotischem Laufzeitverhalten, den es wohl nicht gibt
c) einen exakten Algorithmus mit gleichem asymptotischem Laufzeitverhalten, aber besserem Vorfaktor - schwierig, da Du nicht viel über Deine Algorithmus aussagst
d) eine bessere Implementierung

Es ist etwas mühsam, wenn Du nicht genau sagst, was Du willst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 142
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2021-05-20


Tut mir Leid, ich werde in Zukunft darauf achten etwaiges kenntlich werden zu lassen :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6855
Wohnort: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2021-05-22


Danke :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
dvdlly wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]