Kartesisches Produkt rekursiv programmieren?
Hallo, ich soll zur Übung eine Funktion schreiben, welche das Kartesische Produkt zweier Mengen bildet:
funktion(menge1, menge2)
Ein Bsp: M1 = (1 2 3), M2 = (4 5)
Dann sollte die Funktion folgendes liefern, wobei die Reihenfolge natürlich egal ist: M3 = ((1 4) (1 5) (2 4) (2 5) (3 4) (4 5))
Ich habe leider echt keine Idee wie ich das lösen soll, ohne Schleifen oder extra Variablen zu verwenden. Ich kann ja nicht die Elemente aus den Listen löschen, weil ich sie ja mehrmals benötige.
Hat da jemand einen Ansatz für mich?
5 Antworten
Sagt Dir Tail-Recursion etwas?
Generell:
for (int i=0;cond;++i)
->
f(i)
cond? return
return i+f(i-1)
Dies mußt Du nur entsprechend für Deine Sprache machen. Das Ergebnis mag nicht die hübscheste Rekursion für das kart. Produkt sein, sie wird aber funktionieren.
Und es gibt verschiedene Formulierungen, sollte auch klar sein.
Danke, aber es wären ja 2 verschachtelte Schleifen, und die 2 Parameter der Funktion müssen die Listen sein und keine Schleifenvariablen :)
Zusätzlich gibt es in meiner Sprache keine Voids, also muss alles etwas zurückgeben
Joa, nur ist das dort eben auch nicht rekursiv gemacht. Mit Schleifen wäre es ja kein Problem :)
Habe mal zur Abwechslung ein bißchen in CLISP codiert. Schöne Übung! Es sind zwei rekursive Funktionen geworden. LISP-Experten werden es wohl kürzer und eleganter hinbekommen.
(defun einfach (sym li)
(cond
((equal li nil)
nil
)
(t
(append
(list (list sym (car li)))
(einfach sym (cdr li))
)
)
)
)
(defun kartesisch (li1 li2)
(cond
((equal li1 nil)
nil
)
(t
(append
(einfach (car li1) li2)
(kartesisch (cdr li1) li2)
)
)
)
)
(print (kartesisch '(1 2 3) '(4 5)))
Welche Programmiersprache benutzt du? Meine Idee, wobei ich nicht weiß ob sie funktioniert, ist diese:
f(M1,M2) = {(M1.[1], M2.[1])} U f(M1,M2\M2.[1]) U f(M1\M1.[1], {M2.[1]})
M1.[1] ist das erste Element von 1.
U = Vereinigung und M1\M1.[1] ist die Menge M1 ohne das "erste" Element der Menge.
Abbruchbedingungen f({}, M) = {}, f(M,{}) = {}
Naja, noch nicht so wirklich :)
Bei der letzten Vereinigung, warum wird da nur noch das erste Element statt der Liste verwendet?
Ich habe schon einen Gedanken dahinter, ist aber so etwas schwer zu erklären. Wir nehmen ja (auf das Bespiel bezogen) (1,4) U f({1,2,3}, {5}) U f({2,3},{4})
Es sorgt also dafür, dass auch die anderen Elemente aus M1 außer 1 ein Tupel mit 4 bilden. Probiers vielleicht mal im Kopf aus, dann ergibt das, hoffentlich, Sinn.
P.S.: M1\M1.[1] müsste im math. Sinne eigentlich M1\{M1.[1]} heißen.
P.P.S.: du kannst auch mal den Code reinschicken, ich kenne zwar als funktionale Sprache nur etwas Haskell, aber vielleicht verstehe ich ja etwas.
https://www.minpic.de/i/9e35/8gg6u
Eingabe: (kart '(1 2 3) '(4 5))
Ausgabe: '(5 1 2 4 3)
Vielleicht kommst du damit ja einigermaßen zurecht und findest meinen Fehler ^^
ja, cdr bildet eben den Rest der Liste, also alles außer das erste Element.
Und union macht die Vereinigungsmenge
(list (car y)) nimmt das erste Element aus y und packt es in eine Liste. Also haben wir z.B. car y = 1 --> (list (car y)) = (1)
Mit cons fügen wir dieser Liste vorne etwas an, also wird daraus (4 1).
Mir fällt gerade auf, dass das falsch herum ist, aber das zu ändern ist nicht schwer
Reihenfolge stimmt doch, hatte grad nen kleinen Denkfehler
Der Rest der Liste wird sicherlich als Liste zurückgegeben, gehe ich mal schwer von aus. Was ich noch nicht ganz verstehe ist, einerseits die Klammerung, macht es einen Unterschied, ob da (x) oder x steht bzw. was ist der Unterschied zwischen list und ()? Weil manchmal klammerst du Mengen und manchmal nicht. Zudem verstehe ich das (list (car y)) = (1) nicht, du möchtest als Ergebnis von diesem Aufruf ja {(1,4)} haben, somit bekommst du aber doch {(1,(4))} ?
Wenn etwas mit einer Klammer beginnt wird dieser ausdruck ausgewertet.
Wenn man davor noch ein ' setzt, dann kann man damit Listen angeben.
Bsp: in normalen Programmiersprachen: cdr(list) = ...
hier: (cdr list) = ...
Es ist einfach die Art, Funktionen aufzurufen.
(list x) macht aus x eine Liste. Also wenn x z.B. 1 ist, wird daraus die Liste mit dem Element 1 = '(1)
und mit cons fügt man dieser noch ein Element VORNE hinzu, also ist (cons x '(1)) = '(x 1)
In normalen Programmiersprachen wäre dann also die Liste an der ersten Stelle = x und an der 2. Stelle = 1
hier wird das halt mit einem Leerzeichen getrennt
Versuche es mal mit list(cons (car x) (list (car x))) statt nur cons (car x) (list (car x)).
Du unterscheidest ja nicht zwischen Menge und Tupel und an der Stelle möchtest du ja eigentlich {(1,4)} bzw. ((1,4)) haben und nicht nur (1,4).
Wobei mir schon nicht klar ist, warum '(5 1 2 4 3) rauskommt, die 5 am Angang scheint mir ziemlich komisch :P
Wie bist du eigentlich auf diese Darstellung gekommen? So im Nachhinein macht das Sinn, aber auf die Idee zu kommen... Oh je ^^
(1,1) (1,2) (2,1) (2,2) (3,1) (3,2)
fct(m1,m2,in1,in2, end1, end2, lsn) {
lsn = lsn.add(m1[in1], m2[in2])
if (in1 == end1 & in2 ==end2) {
return lsn
}
in2 = (in2 mod 2) + 1
in1 = -(in2-2)+in1
return fct(m1, m2, in1, in2,end1, end2 lsn)
}
PSEUDOCODE AUS DEM KOPF HOFFE DIE IDEE IST KLAR
Scheme / LISP
Die Vereinigungsmenge habe ich schon geschrieben, also teste ich das mal :)
Danke