Results 1 to 13 of 13
  1. #1
    daff's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Location
    Wien (die große Stadt)
    Posts
    1,263
    Thanks Thanks Given 
    40
    Thanks Thanks Received 
    35
    Thanked in
    17 Posts

    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.
    Restrain the specimen!

  2. #2
    TheButcher's Avatar
    Title
    Elite
    Join Date
    Dec 2003
    Location
    Vienna
    Posts
    462
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Quote Originally Posted by 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

  3. #3
    daff's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Location
    Wien (die große Stadt)
    Posts
    1,263
    Thanks Thanks Given 
    40
    Thanks Thanks Received 
    35
    Thanked in
    17 Posts
    Hätt ich eben auch nicht gesagt, aber wissen das auch die Leutchen, die die Testfälle zur Beurteilung schreiben? Weiß das der Praktikant, der die Angaben geschrieben hat?
    Restrain the specimen!

  4. #4
    THE_ONE's Avatar
    Title
    Master
    Join Date
    Mar 2004
    Location
    Vienna
    Posts
    170
    Thanks Thanks Given 
    2
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    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
    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.

  5. #5

    Title
    Principal
    Join Date
    Sep 2005
    Posts
    78
    Thanks Thanks Given 
    6
    Thanks Thanks Received 
    2
    Thanked in
    2 Posts
    also irgendwie versteh ich die angabe nicht ganz. sind 2 strings nicht permutationsaehnlich, wenn sie die gleichen zeichen (nur willkuerlich vermischt) enthalten?!?

    oder was heist das?

  6. #6
    daff's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Location
    Wien (die große Stadt)
    Posts
    1,263
    Thanks Thanks Given 
    40
    Thanks Thanks Received 
    35
    Thanked in
    17 Posts
    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.
    Restrain the specimen!

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    In der englischen wikipedia steht das eigentlich ganz eindeutig:
    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 )
    Last edited by Chris; 21-11-2005 at 16:01.
    hi, i'm a signature virus. copy me into your signature to help me spread.

  8. #8
    Plantschkuh!'s Avatar
    Title
    Dipl.Ing
    Join Date
    Jun 2003
    Location
    mal hier, mal da
    Posts
    2,587
    Thanks Thanks Given 
    366
    Thanks Thanks Received 
    498
    Thanked in
    324 Posts
    Quote Originally Posted by daff
    Grundsätzlich ist eine Permutation die Umordnung (Reihenfolgenänderung) der Elemente einer Menge.
    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.)
    *plantsch*

  9. #9
    daff's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Location
    Wien (die große Stadt)
    Posts
    1,263
    Thanks Thanks Given 
    40
    Thanks Thanks Received 
    35
    Thanked in
    17 Posts
    Quote Originally Posted by 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?
    Quote Originally Posted by 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
    Restrain the specimen!

  10. #10

    Title
    Master
    Join Date
    Oct 2003
    Posts
    144
    Thanks Thanks Given 
    2
    Thanks Thanks Received 
    3
    Thanked in
    2 Posts
    Hi,

    Ich finde die Angabe ausnahmsweise mal recht klar:

    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
    Last edited by Maggot; 21-11-2005 at 17:14.
    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?

  11. #11
    Plantschkuh!'s Avatar
    Title
    Dipl.Ing
    Join Date
    Jun 2003
    Location
    mal hier, mal da
    Posts
    2,587
    Thanks Thanks Given 
    366
    Thanks Thanks Received 
    498
    Thanked in
    324 Posts
    Quote Originally Posted by 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.)

    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.)
    *plantsch*

  12. #12

    Title
    Hero
    Join Date
    Mar 2003
    Posts
    213
    Thanks Thanks Given 
    1
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    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!

  13. #13

    Title
    Principal
    Join Date
    Apr 2005
    Posts
    83
    Thanks Thanks Given 
    0
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    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,

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •