Beispiel 4.2.1 -- sind "abc" und "aabbcc" permutationsähnlich?

  • Hab folgendes auch in die Newsgroup gepostet, aber das war vermutlich eh vergebliche Liebesmüh:


    Wie sieht es aus, sind hier echte Mengen oder Multimengen von Zeichen gemeint, wenn man das so sagen kann?


    Sprich: sind "abc" und "aaccbb" permutationsähnlich oder nur "abc" und "acb" (und natürlich auch "cab" und "bac" und so weiter)? Können also Zeichen "wiederverwendet" werden oder nicht?


    Werd am Montag einen Tutor bejammern gehen, aber rein von der Angabe her ist es schwer zu sagen, was da jetzt gemeint ist.

  • Zitat von daff


    Sprich: sind "abc" und "aaccbb" permutationsähnlich oder nur "abc" und "acb" (und natürlich auch "cab" und "bac" und so weiter)?


    Natürlich sind "abc" und "aaccbb" NICHT permAehnlich. Wenn du die Anz von den Perm berechnest bekommst du für "abc" - 6 und für "aabbcc" - 90

  • Heißt das jetzt einfach dass die Anzahl der verschiedenen Charakter in beiden Strings gleich sein muß
    bsp: "aabbbc" anzahl(a) = 2 anzahl(b) = 3 anzahl(c) = 1
    "aaabbbc" anzahl(a) = 3 anzahl(b) = 3 anzahl(c) = 1
    da die Anzahl der a's im ersten String nicht gleich der Anzahl der a's im zweiten String ist, sind die beiden Strings nicht permutaionsähnlich!!
    reicht das oder brauch ich noch was??
    MFG THE_ONE

    :engel:Seit anbeginn von windows fing die Menschheit an zu verblöden: Windows 95 was unable to detect your Keyboard, press F1 or F2 to abort.

  • Tja, kommt drauf an, was mit der Angabe gemeint ist. Grundsätzlich ist eine Permutation die Umordnung (Reihenfolgenänderung) der Elemente einer Menge. "Blumentopf" ist eine Permutation von "topfBlumen" und von "toBlumenpf" und so. "Blumentopf" und "topfBlumen" und "toBlumenpf" sind also laut Angabe permutationsähnlich.


    Was ist dann aber mit dem String "Blumumumentopf"? Sind dieser String und der String "Blumentopf" permutationsähnlich? Ich würde sagen, rein mengentheoretisch betrachtet, ja.


    Warum? Weil die Menge von Zeichen, die den String "Blumumumentopf" ausmacht genau folgende ist: {"B","e","f","l","m","n","o","p","t","u"}. Und die Menge von Zeichen, die den String "Blumentopf" ausmacht ist ebenfalls genau das: {"B","e","f","l","m","n","o","p","t","u"}. Zur Erinnerung: Mengen sind die "Zusammenfassung von bestimmten wohl unterschiedenen Objekten der Anschauung oder des Denkens, welche die Elemente der Menge genannt werden, zu einem Ganzen". In Mengen gibt es ebenfalls keine Mehrfachvorkommen der einzelnen Elemente. Deswegen ist die Menge der Zeichen, die den String "Blumentopf" ausmacht die gleiche Menge, die den String "Blumumumentopf" ausmacht.


    Ich denke ja nicht, dass derjenige, der die Angabe geschrieben hat, das auch so gesehen hat. (Würde mich wundern.) Aber wenn man schon von Permutationen spricht, und nicht explizit dazusagt, dass man die Elemente von Multimengen permutiert, dann geht es, per Definition, um Mengen. Das heißt eben, dass "abc" und "aabbcc" permutationsähnlich sind.


    Nicht, dass das Ganze von der Implementierung her in Haskell ein Problem darstellt (sort und nub, oder halt ohne nub, je nachdem was gemeint ist), aber so wie die Punktevergabe in der VL gehandhabt wird, und bei der Sorgfalt (oder dem Fehlen davon), mit der oft die Angabe und die Testfälle vorbereitet werden, muss man schon vorsichtig sein und sich um jeden Punkt Sorgen machen.

  • In der englischen wikipedia steht das eigentlich ganz eindeutig:

    Zitat

    A permutation is an ordered sequence containing each symbol from a set once and only once; neither "1, 2, 2, 3, 4, 5, 6" nor "1, 2, 4, 5, 6" are permutations.


    wenn also zB "aaabbbcc" keine permutation ist, wird es auch zu nichts permutationsaehnlich sein...


    ob das im sinne der testfaelle ist, ist eine andere frage; allerdings gibts einen guten rueckhalt, wenn man nachher mit dem prof. knoop um die punkte streitet ;))

  • Zitat von Plantschkuh!

    Das mal grundsätzlich bestimmt nicht, denn die Elemente einer Menge haben keine Reihenfolge. (Daher ist auch der erste informelle Satz von http://de.wikipedia.org/wiki/Permutation falsch; die formalen Definitionen sind in Ordnung.)


    Stimmt natürlich, die auf die Elemente der Menge selbst ist keine Reihenfolge (oder Ordnung?) festgelegt. Mein Fehler (und dabei hab ich diesen informellen Satz nichtmal gelesen). Hätte vielleicht schreiben müssen "die Umordnung der Elemente einer Menge in einer Folge" oder so. Einen String kann man ja als Folge von Elementen einer Menge bezeichnen, hoff ich. Anyway, der Rest meines Rants war richtig, ja?

    Zitat von chris


    ob das im sinne der testfaelle ist, ist eine andere frage; allerdings gibts einen guten rueckhalt, wenn man nachher mit dem prof. knoop um die punkte streitet)


    Streitet man irgendwann mit Prof. Knoop um die Punkte? Bei der mündlichen Prüfung oder so? Wär ja krass :)

  • Hi,


    Ich finde die Angabe ausnahmsweise mal recht klar:


    Zitat

    Zwei Zeichenreihen heißen einzeichenähnlich GENAU dann,
    wenn jede der Zeichenreihen durch Auslassen bzw. Einfügen GENAU eines
    Zeichens in die jeweils andere Zeichenreihe übergeht


    bedeutet ja nichts anderes als: wenn die Reihe ein Element mehr hat als die
    andere und die Mengen ohne dem Element Ident sind ist die Zeichenreihe einzeichenähnlich (sagt der Name ja auch)


    Und eine Permutation muss laut Definition immer die gleiche Menge an Elementen enthalten, wobei die Benennung der Elemente nicht von Bedeutung ist. Demnach ist "aaa" = "123" und nicht "1" ! (ich bin mir jetzt nicht sicher aber die Mengen sollten doch Bijektiv zueinander sein ?!) demnach kann eine Menge gar nicht kleiner sein als die Andere.


    mfg,


    Maggot

    Lumbergh: "Mm, yeah. You see, we're putting the cover sheets on all T.P.S. reports now before they go out. Did you see the memo abouth this?

  • Zitat von daff

    Einen String kann man ja als Folge von Elementen einer Menge bezeichnen, hoff ich. Anyway, der Rest meines Rants war richtig, ja?


    Hmm, ich kann mir keine Permutation einer Multimenge vorstellen, also weiß ich nicht, inwieweit der Rant richtig war.
    Generell ist der Begriff der Menge hier auch überflüssig, denke ich. Die zentrale Frage ist, was ist eine Permutation einer Liste? Ich behaupte mal, in der Informatik wird darunter üblicherweise eine Permutation der Elementpositionen verstanden, also ohne Eliminierung von gleichen Elementen. Ich bin mir eigentlich sicher, daß die Angabe so gemeint ist. (Aber bei mir gehts ja um nix.)


    Zitat

    Streitet man irgendwann mit Prof. Knoop um die Punkte? Bei der mündlichen Prüfung oder so? Wär ja krass :)


    Streit mag er glaub ich nicht so, aber man kann sicher mit ihm drüber reden. Ausdrucke der Beispiele muß man sowieso mitnehmen, also wenn man sich wo ungerecht behandelt fühlt oder irgendwo einen winzigen Bug in einem prinzipiell richtigen Programm hatte, kann man ihm das zumindest zeigen.
    (Das gilt aber ziemlich sicher nicht für die ich-habe-Angst-vor-der-0-und-behandle-sie-daher-nicht-sinnvoll-Partie.)

  • heißt das jetzt, dass "asdf" und "fdsa1" einzeichenähnlich wären - also ich habs so verstanden, dass die Strings total ident sein müssen und bei einem an einer Stelle ein Zeichen mehr drin vorkommen darf! (z.B. "Blume" und "Blueme")


    naja egal - ich wart mal auf die Bewertung - es wäre wirklich mal schön von der Übungsleitung 3-4 Testfälle zu bekommen, damit man die Angabe genau einordnen kann!

  • aaalso ... ich war heut mal im labor und hab gefragt wegen der permuation:
    der tutor dort hat gemeint er hats wie eine permutation von multimengen verstanden, also
    "abc" und "aabbcc" sind NICHT permutationsähnlich
    "aabbcc" und "bacacb" zb. schon


    also soll die eine zeichenreihe einfach eine umordnung der andren sein.


    mfg,