HA3 7

[ChRiZz88]

Joa, ich habs ja schon.. Jetzt noch perm... mal überlegen^^

[Skylo]

hmmmmmm! perm bereitet mir noch probleme in der Umsetzung!

[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

[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...

[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.

[ChRiZz88]

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

[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!

[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

[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!

[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

[mantra]

ich hab grad überlegt:

Hast du niemanden, mit dem du die Übungen zusammen bearbeiten kannst?

[Skylo]

nee brauch ich nich ich wiederhol ja eigentlich nur

[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...

[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?

[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