Aufgabe 11.5: Buchstabenmix

system · July 5, 2014, 3:38pm

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

EloquentProf · July 5, 2014, 3:38pm

Aufgabe 11.5: Buchstabenmix
Hallo allerseits,

Ich habe die Aufgabe bis auf die c bereits ergfolgreich implementiert, aber irgendwie komme ich jetzt partou nicht weiter. Ich komme einfach nicht drauf wie ich bei der c die listen nacheinander erzeuge.

Meine Vermutung bis jetzt ist, dass ich erst zuerst alle listen für n = 1 erzeuge, also zB für das Wort “Inf” wäre das

List(List(‘I’), List(‘n’), List(‘f’))

Und dann aus dieser mit Hilfe von mixInWords die listen für n = 2 also

List(List(n, f), nList(f, n), List(I, n), List(n, I), List(I, f), List(f, I))

und aus dieser dann wiederum n = 3 etc.

Leider komme ich absolut nicht darauf wie ich aus der Liste von n=2 auf die Liste von n=3 komme.

Kann mir jemand helfen, oder ist meine Grundannahme dass ich die Teile aufeinander aufbauen lasse schon Mist?

Alicen · July 5, 2014, 3:43pm

Die Idee ist zwar, wenn man sich die Lösung anschaut, verlockend…

…aber nicht besonders zielführend.

Tipp: Rekursion. Was ist dein Basisfall, von dem du auf jeden Fall sofort die Lösung weißt, und wie kommst du, wenn du einen Buchstaben dazu nimmst, auf die restlichen Wörter?

Hoffe, du kannst mit den Tipps was anfangen. 11.5c ist die schwierigste des aktuellen Aufgabenblatts (meiner Meinung nach ;))

Alicen

EloquentProf · July 5, 2014, 7:40pm

Okay jetzt also mit rekursion,

leider bringt mich das immernoch kaum weiter, der Basisfall ist Nil und das produziert eine leere Liste das ist schon klar, bloß habe ich keine Ahnung bei der Rekursionsbedingung.

Meine Jetztige führt mich zum Ergebnis:

List(List(I), List(n), List(f), List(n, f), List(f, n), List(I, n, f), List(n, I, f), List(n, f, I))

Wo ich aber jetzt noch die anderen herbekommen soll ist mir schleierhaft

Alicen · July 6, 2014, 7:56am

Du hast es bereits fast.

Jetzt musst du dir nur noch überlegen, warum beispielsweise (n, f) verloren geht, das ja schonmal da war, und das behebst du dann als letztes noch.

EloquentProf · July 6, 2014, 11:34am

Wie meinen?

n,f ist noch nie verloren gegangen???

Sorry aber das hilft mir überhaupt nicht xD

_Ralf · July 6, 2014, 12:03pm

Überleg dir mal, in was du das aktuelle Zeichen einsortieren musst. Das ist ja nicht einfach nur die Zeichenkette dahinter.

Bassbauer · July 6, 2014, 1:48pm

Ich hab genau das gleiche Problem und komm mit den Hilfestellungen auch nicht weiter, evtl. kann jemand eine etwas ausführlichere Erklärung abgeben ?

Basisfall ist klar, aber man muss ja irgendwie nur 1 Buchstabe aus dem wort rausnehmen und es danach wieder reinstecken.

mixInWords I, nf
mixInWords n, If
mixInWords f, In
sowie dann das gleich fuer nf unf f ?

bin schon ganz verwirrt :-S

Bass

EloquentProf · July 6, 2014, 1:49pm

Das ist ja genau mein Problem, ich verstehe absolut nicht WIE die Funktion eigentlich genau WAS macht.

Ich wüsste sehr einfach wie ich das ganze ohne die mixInWords bewerkstellige, aber ich finde die Anfoderung dass ich mix InWords benutzen muss eher unhilfreich.

Kann mir bitte jemand einfach erklären egal ob pseudocode oder prosa wie die funktion das ergebnis bewerkstelligen soll? Denn ich komme absolut nicht drauf wie das mit Hilfe von mixInWords funktionieren soll.

Edit:
Okay sorry das war ein wenig genervt, aber es ist leider echt so dass diese Aufgabe praktisch nicht erklärt ist wie sie funktionieren soll.
Ich editier hier gleich noch weiter meine Gedankengängen vielleicht kann mir dann ja jemand den Weg weisen.

Edit 2:
Also für die 2er Kombinationen würde ich einfach zum Beispiel beim Wort „Inf“ kombinieren:

Beim aktuellen Element also „I“ mit jedem der folgenden, also „I“ mit „n“ und „I“ mit „f“
Bei den folgenden elementen genau dasselbe, das aktuelle element mit allen folgenden einzeln, in diesem Fall „n“ mit „f“
Wenn es keine weiteren folgenden gibt wird nichts kombiniert.

Dafür brauche ich mixInWords nicht, dafür reicht einfach mixIn

mein Problem ist jetzt ich habe keine Ahnung wie ich die 3er und noch höhrere kombinationen überhaupt mit mixInWords bilde.

_Ralf · July 6, 2014, 3:18pm

Ich hab dafür auch ewig gebraucht, also macht euch keine Sorgen.

Da das ganze ja rekursiv abläuft, musst du am besten “von rechts” ran gehen. Die Listen kommen dann so zurück:

[m]f[/m] einsortieren in eine leere Liste.
[m]n[/m] einsortieren in das davor, also [m]f[/m]
[m]I[/m] einsortieren in das davor, also [m]nf[/m] und [m]fn[/m]

Gleichzeitig mit jedem Schritt speicherst du natürlich auch das aktuelle Element und die Liste, in die einsortiert wird (sofern vorhanden).

EloquentProf · July 6, 2014, 8:28pm

Bist du sicher, dass du das ganze ohne var umgesetzt hast Ralf? Und bist du sicher das das auch mit Wörtern von länge 4 oder mehr funktioniert?

Könnte einer der Tutoren bitte testen ob der Algorithmus der Lösung auch für Permutationen 4 oder mehr funktioniert. Denn alles was ich mir denke wird ab Länge 4 unglaublich messy und absolut nicht einfach zu behandeln

_Ralf · July 7, 2014, 11:13am

Ja und ja. Absolut sicher. Bei „Info“ kommen die 64 richtigen Wörter raus, bei „Infos“ 325 und bei „0123456789“ 9864100 verschiedene Wörter. Ob das stimmt kannst du ja selbst nachrechnen

In meiner [m]mix[/m]-Funktion sind das drei cases, wovon der letzte drei Listen konkateniert (wie oben beschrieben). Messy ist da nix.

edit: zum prüfen kann man übrigens auch [m]List.distinct[/m] verwenden, solange man nur verschiedene Zeichen verwendet (Foo erzeugt ja Unterlisten, die gleich sind). Wie oben genannt kommen dann bei „0123456789“ 9864100 verschiedene Elemente raus.

lemur · July 9, 2014, 6:33am

ich häng leider schon bei Character-Mix bei Teilaufgabe 1.
ich glaube aber, dass es hauptsächlich ein syntax-problem ist.
wie kann ich denn einer List[List[Char]] namens ls eine List[Char] anhängen?
geht das mit :: oder mit :::? ich hab schon ganz viele variationen ausprobiert und
keine hat funktioniert

EDIT:
Ich muss mich korrigieren. Mein Problem ist, dass mir die Funktionen drop und take so wie ich sie anwende,
eine List[Any] zurückgeben und keine List[Char]. Kann oder muss man das casten?

EDIT:
Hat sich schon erledigt

Charbacca · July 9, 2014, 1:10pm

Wie hat sich’s denn erledigt? Hab mit dem List[Char] an eine List[List[Char]] anhängen auch so meine Probleme…

lemur · July 9, 2014, 1:22pm

also ich gehe mal davon aus, dass du’s hast wie ich. dann müsstest du ja auch so eine monster-konkatenation haben.
die habe ich in eine hilfsfunktion ausgelagert, die mir eine List[Char] zurückgibt. und nach dem aufruf der hilfsfunktion
habe ich den rekursiven ausdruck mit :: angehängt. dann hat’s auf einmal funktioniert

_Ralf · July 10, 2014, 12:34pm

Also wie ich das verstanden hab steht in der Angabe ja Verwenden Sie unbedingt eine Listenabstraktion zur Lösung der Aufgabe.
Darum hab ich für die a) ne for-Schleife:

for (i <- foo) yield bar

Wobei [m]i[/m] eben eine normale Laufvariable ist, die über die ganze Liste [m]foo[/m] läuft, und [m]bar[/m] die erzeugten Wörter sind. Aus denen muss man halt noch ne Liste machen.

Ferron · July 10, 2014, 5:09pm

Hab das wie du, bei mir sind ebenfalls die list.distinct.length werte gleich den list.length werten.

Problem ist aber: Bei Wörtern länger 3 stimmt die Reihenfolge in der Liste (zumindest bei mir) nicht mehr, vorausgesetzt es sollen erst alle einzelnen, dann alle 2er, dann alle 3er, dann alle 4er Kombis gelistet werden.

zB. ergibt bei mir

 mix("1234".toList

List(List(1), List(2), List(3), List(4), List(3, 4), List(4, 3), List(2, 3), List(3, 2), List(2, 4), List(4, 2), List(2, 3, 4), List(3, 2, 4), List(3, 4, 2), List(2, 4, 3), List(4, 2, 3), List(4, 3, 2), List(1, 2), List(2, 1), List(1, 3), List(3, 1), List(1, 4), List(4, 1), List(1, 3, 4) (...)

Sieht das bei dir auch so aus? Ist das erlaubt?

EloquentProf · July 11, 2014, 1:20am

Ich bin leider immernoch nicht draufgekommen wie es geht, muss allerdings auch sagen, dass ich wegen anderer Kurse nicht mehr wirklich Zeit investiert habe.

Könnte jemand bitte nach Ablauf der Abgabe mal seinen Code posten, würde das ganze gerne zumindest nachvollziehen.

_Ralf · July 11, 2014, 11:20am

Von sortiert stand in der Angabe nichts. Bei mir sind auch weiter hinten ein paar kürzere Tupel. Das sollte okay sein.

object CharMix extends App{
	def mixIn: (Char, List[Char]) => List[List[Char]] = {
		case (c, Nil) => List(List(c))
		case (c, cs) => (for (i <- 0 until cs.length+1) yield cs.take(i) ::: c :: cs.drop(i)).toList
	}
	
	def mixInWords: (Char, List[List[Char]]) => List[List[Char]] = {
		(c, cs) => for (list <- cs; word <- mixIn(c, list)) yield word
	}	
	
	def mix: List[Char] => List[List[Char]] = {
		case Nil => Nil
		case h :: Nil => List(List(h))
		case cs => 
			List(List(cs.head)) :::				// aktuell erster Buchstabe
			mix(cs.tail) ::: 					// rekursiv weiter mit naechsten Buchstaben
			mixInWords(cs.head, mix(cs.tail)) 	// aktuellen Buchstaben in darauf folgende Liste mischen
	}
}

Ferron · July 11, 2014, 1:26pm

Hier mal meine Version zum Vergleich:

object CharMix {
	def mixIn : (Char, List[Char]) => List[List[Char]] = (c, cs) => {
		def mixInHelper: (Int, Char, List[Char]) => List[Char] = (i, c, cs) =>  cs.take(i):::(c::cs.drop(i))
		
		(for (i <- 0 to cs.length) yield mixInHelper(i, c, cs)).toList	
	}
	
	def mixInWords: (Char, List[List[Char]]) => List[List[Char]] = (c, css) => css match {
	  	case Nil => Nil
	  	case cs::xss => mixIn(c, cs):::mixInWords(c, xss)
	}
	
	def mix : List[Char] => List[List[Char]] = cs => cs match {
		case Nil => Nil
		case c::Nil => mixInWords(c, List(Nil))
		case c::xs =>  mixInWords(c, List(Nil)):::mix(xs)::: mixInWords(c, mix(xs))
	}
	
}