Seite 3 von 7

Verfasst: 12. Nov 2007 21:42
von ChRiZz88
Joa, ich habs ja schon.. Jetzt noch perm... mal überlegen^^

Verfasst: 13. Nov 2007 19:31
von Skylo
hmmmmmm! perm bereitet mir noch probleme in der Umsetzung!

Verfasst: 13. Nov 2007 20:09
von Skylo
(list (list (list 1 2 3) (list 2 1 3) (list 2 3 1)) (list (list 2 3) (list 3 2)) empty)
Mein Ergebnis bisher, ich kann irgendwie nich am Ende noch das erste Element beibehalten

Verfasst: 13. Nov 2007 21:30
von ChRiZz88
Hmm, also bei (perm ..) fallen mir spontan zwei mögliche Ansätze ein, die aber beide so ihre Probleme haben...

1. Ansatz (auch auf dem Arbeitsblatt beschrieben):
Ans Ende der Liste gehen, bis die Liste nur noch aus einem Element besteht. Dann das vorhergehende Element mit insert-everywhere überall einfügen. Rekursiv das Element davor in die beiden erhaltenen Listen einfügen. Terminierungsfall, wenn man vorne an der Liste angekommen ist.
Problem: Zugriff auf die erhaltenen Listen? Exakter Zugriff auf ein bestimmtes Element der Liste?
Beispiel: '(1 2 3) --> 3 --> 2 3 ; 3 2 --> 1 2 3 ; 2 1 3; 2 3 1; 1 3 2; 3 1 2; 3 2 1

2. Ansatz:
Erstes Element mit insert-everywhere überall einfügen. Rekursiv jedes weitere Element ebenfalls überall einfügen. Terminierung, wenn die Liste leer ist.
Problem: Redundanz, Verdopplung, da das einzusetzende Element sich ja noch in der Liste befindet. Funktion zuerst nötig, die ein Element vorübergehend aus einer Liste entfernt.

Meiner Ansicht nach führt der zweite Ansatz zu nix und beim ersten habe ich so meine Implementationsschwierigkeiten...

Verfasst: 13. Nov 2007 23:40
von Demmi
Ich hab perm mit dem 1. Ansatz von ChRiZz88 bzw. dem Weg auf dem Arbeitsblatt geschafft. Ich hab mich haber auch arg lange dran aufgehalten.

Ich habs dann so gelöst, dass sich perm unterschiedlich verhält, je nach dem wie lange die Liste ist die reinkommt.
Für Empty, L=1 und L=2 kann man das nämlich ganz gut vordefinieren.
Alles andere löse ich mit map und nem Selbstaufruf von perm.
Anders als auf diese Weise hab ich es leider noch nicht zum laufen bekommen.

Edit: Ach ja, flatten-once spielt auch noch ne Rolle.

Verfasst: 14. Nov 2007 00:15
von ChRiZz88
Demmi hat geschrieben:Alles andere löse ich mit map und nem Selbstaufruf von perm.
Und genau darum gehts bei der ganzen Aufgabe xD Das is das ganze Rätsel, hmm Oo

Verfasst: 14. Nov 2007 02:15
von Skylo
hmmm also bei mir kommt mitlerweile soviel raus...
empty
(list 1)
(list (list 1 2) (list 2 1) (list 2 2) (list 2 2))
(list
(list 1 (list 2 3) (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) 1 (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) 1 (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) 1 (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) (list 3 3) 1)
(list 2 (list 2 3) (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) 2 (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) 2 (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) 2 (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) (list 3 3) 2)
(list 3 (list 2 3) (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) 3 (list 3 2) (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) 3 (list 3 3) (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) 3 (list 3 3))
(list (list 2 3) (list 3 2) (list 3 3) (list 3 3) 3))
>
Nach jeweils folgenden Befehlen
(perm '())
(perm '(1))
(perm '(1 2))
(perm '(1 2 3 ))
Ich weiss nich wo mein Fehler nun noch steckt, aber sicherlich wird irgendwo zu oft aufgerufen , schätze ich mal... flatten-once hab ich auch nicht angewendet btw bisher!

Verfasst: 14. Nov 2007 10:25
von ChRiZz88
Mh joa, bei mir siehts da auch nur wenig besser aus...
Bei (perm '(1 2 3)) erhalte ich:

(list (list (list 1 2 3) (list 2 1 3) (list 2 3 1)) (list (list 2 2 3) (list 2 2 3) (list 2 3 2)) (list (list 3 2 3) (list 2 3 3) (list 2 3 3)))

bis nach der dritten Unterliste ist das alles korrekt, aber dann verliert er die 1^^ Ist auch nach dem zweiten Ansatz programmiert, weil ich mit dem ersten implementierungstechnisch gar nich zurechtkomm Oo

Verfasst: 14. Nov 2007 12:44
von Skylo
ich hab grad überlegt:

Man muss eigentlich die Methode (insert-everwhere) so einrichten das sie auch mit mehreren Listen zurecht kommt.

Bsp: (insert-everwhere 'x (1 2 3) (4 5 6))
muss eigentlich nicht

( ('x (1 2 3) ) ((1 2 3 ) 'x (4 5 6 )) ((1 2 3) (4 5 6) 'x))
rauskommen sondern meiner Meinung nach

wird 'x auch passend in jede Unterliste eingefügt....

Sprich es kommen viel mehr möglichkeiten raus, in unserem Fall 8.

Ich arbeite grad daran meine (insert-everwhere ) dahingehend umzubauen.

D.h. man checkt zusätzlich ob das erste element eine Liste ist mit "cons?" und ruft schon dann rekursiv (insert-everywhere ) auf.

Ich versuchs mal!

Verfasst: 14. Nov 2007 12:57
von Skylo
(list (list 1 2) (list 2 1) (list 2 2) (list 2 2))
(list
(list (list 1 2 3) (list 2 1 3) (list 2 3 1))
(list (list 1 3 2) (list 3 1 2) (list 3 2 1))
(list (list 1 3 3) (list 3 1 3) (list 3 3 1))
(list (list 1 3 3) (list 3 1 3) (list 3 3 1))
(list (list 2 2 3) (list 2 2 3) (list 2 3 2))
(list (list 2 3 2) (list 3 2 2) (list 3 2 2))
(list (list 2 3 3) (list 3 2 3) (list 3 3 2))
(list (list 2 3 3) (list 3 2 3) (list 3 3 2))
(list (list 3 2 3) (list 2 3 3) (list 2 3 3))
(list (list 3 3 2) (list 3 3 2) (list 3 2 3))
(list (list 3 3 3) (list 3 3 3) (list 3 3 3))
(list (list 3 3 3) (list 3 3 3) (list 3 3 3)))
Die ersten 6 (2) ergebnisse sind doch nun richtig ;)

Verfasst: 14. Nov 2007 13:58
von mantra
Skylo hat geschrieben:ich hab grad überlegt:
Hast du niemanden, mit dem du die Übungen zusammen bearbeiten kannst?

Verfasst: 14. Nov 2007 14:29
von Skylo
nee brauch ich nich ;) ich wiederhol ja eigentlich nur ;)

Verfasst: 14. Nov 2007 17:49
von acidicX
Also ich hab auch quasi nach dem 2. Ansatz programmiert, allerdings habe ich eben das Problem dass

Code: Alles auswählen

(perm '(3 2 1))
(list
 (list (list 3 2 1) (list 2 3 1) (list 2 1 3))
 (list (list 2 3 1) (list 3 2 1) (list 3 1 2))
 (list (list 1 3 2) (list 3 1 2) (list 3 2 1)))
sich Redundanzen bilden.. auf einen anderen Weg bzw. den "1. Ansatz" hier bin ich noch nicht wirklich gekommen bzw steig nicht ganz dahinter wie man das machen soll...

Verfasst: 14. Nov 2007 18:12
von ChRiZz88
Trotzdem nicht schlecht, leider fehlt dir auch eine Permutation nämlich '(1 2 3).. Wie haste das gemacht? Also mit welchen Eingaben rekursiert dein Algorithmus?

Verfasst: 14. Nov 2007 18:32
von acidicX
ein map sucht für insert-everywhere alle möglichen positionen raus und übergibt sie dann an insert-everywhere. ist relativ kompliziert mit 2 locals oO