Kartesisches Produkt in clojure

Question

Ich versuche eine Methode zu implementieren, die eine Liste von Listen nimmt und das kartesische Produkt dieser Listen zurückgibt.

Hier ist, was ich bisher:

(defn cart 


([] '()) 
([l1] (map list l1)) 
([l1 l2] 
    (map 
    (fn f[x] (map 
    (fn g [y] (list x y)) 
    l2)) 
     l1) 
    ) 

) 

(defn cartesian-product [& lists] 
     (reduce cart lists) 

) 





;test cases 
(println (cartesian-product '(a b) '(c d))) ; ((a c) (a d) (b c) (b d)) 
(println (cartesian-product())) ;() 
(println (cartesian-product '(0 1))) ; ((0) (1)) 
(println (cartesian-product '(0 1) '(0 1))) ; ((0 0) (0 1) (1 0) (1 1)) 
(println (apply cartesian-product (take 4 (repeat (range 2))))) ;((0 0 0 0) (0 0 0 1) (0 0 1 0) (0 0 1 1) (0 1 0 0) (0 1 0 1) (0 1 1 0) (0 1 1 1) (1 0 0 0) (1 0 0 1) (1 0 1 0) (1 0 1 1) (1 1 0 0) (1 1 0 1) (1 1 1 0) (1 1 1 1)) 

Das Problem ist meine Lösung wirklich ist 'brackety'.

(((a c) (a d)) ((b c) (b d))) 
() 
(0 1) 
(((0 0) (0 1)) ((1 0) (1 1))) 
(((((((0 0) (0 1)) 0) (((0 0) (0 1)) 1)) 0) (((((0 0) (0 1)) 0) (((0 0) (0 1)) 1)) 1)) ((((((1 0) (1 1)) 0) (((1 0) (1 1)) 1)) 0) (((((1 0) (1 1)) 0) (((1 0) (1 1)) 1)) 1))) 

Ich versuchte

 (apply concat(reduce cart lists)) 

Zugabe, aber dann bekomme ich einen Absturz wie so:

((a c) (a d) (b c) (b d)) 
() 
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long clojure.lang.RT.seqFrom (RT.java:494) 

Also, ich glaube, ich bin in der Nähe, aber etwas fehlt. Aber da ich so neu in clojure und funktionaler Programmierung bin, könnte ich auf dem völlig falschen Weg sein. Bitte helfen Sie! :)

Answer 1

Dies ist viel einfacher als für Verständnis zu tun, als indem man versucht, manuell die Rekursion zu arbeiten:

(defn cart [colls] 
    (if (empty? colls) 
    '(()) 
    (for [x (first colls) 
      more (cart (rest colls))] 
     (cons x more)))) 

user> (cart '((a b c) (1 2 3) (black white))) 
((a 1 black) (a 1 white) (a 2 black) (a 2 white) (a 3 black) (a 3 white) 
(b 1 black) (b 1 white) (b 2 black) (b 2 white) (b 3 black) (b 3 white) 
(c 1 black) (c 1 white) (c 2 black) (c 2 white) (c 3 black) (c 3 white)) 

Der Basisfall ist offensichtlich, (es muss eine Liste sein, die leer enthält Liste, nicht die leere Liste selbst, da ist eine Möglichkeit, ein kartesisches Produkt von keiner Listen zu nehmen). Im rekursiven Fall iterieren Sie einfach über jedes Element x der ersten Sammlung und dann über jedes kartesische Produkt des Rests der Listen, wobei Sie das von Ihnen gewählte x voraussetzen.

Answer 2

Aus Gründen des Vergleichs, im Geist der ursprünglichen

(defn cart 
    ([xs] 
    xs) 
    ([xs ys] 
    (mapcat (fn [x] (map (fn [y] (list x y)) ys)) xs)) 
    ([xs ys & more] 
    (mapcat (fn [x] (map (fn [z] (cons x z)) (apply cart (cons ys more)))) xs))) 

(cart '(a b c) '(d e f) '(g h i)) 
;=> ((a d g) (a d h) (a d i) (a e g) (a e h) (a e i) (a f g) (a f h) (a f i) 
; (b d g) (b d h) (b d i) (b e g) (b e h) (b e i) (b f g) (b f h) (b f i) 
; (c d g) (c d h) (c d i) (c e g) (c e h) (c e i) (c f g) (c f h) (c f i)) 

Answer 3

Persönlich würde ich amalloy die for Lösung verwenden. Meine allgemeine Faustregel ist, dass, wenn meine Schleife als einzelner map/filter/etc Aufruf mit einem einfachen Funktionsargument ausgedrückt werden kann (also ein Funktionsname oder eine kurze fn/#() Form), es besser ist, die Funktion zu verwenden. Sobald es komplexer wird, ist ein for Ausdruck viel einfacher zu lesen. Insbesondere ist for viel besser als verschachtelte Karten. Das heißt, wenn ich nicht for hier verwendet haben, das ist, wie ich die Funktion schreiben würde:

(defn cart 
    ([] '(())) 
    ([xs & more] 
    (mapcat #(map (partial cons %) 
        (apply cart more)) 
      xs))) 

Dinge zu beachten: Erstens gibt es keine Notwendigkeit für die reduzieren. Rekursion kann damit gut umgehen.

Zweitens, nur zwei Fälle. Wir können die Funktion in einer leeren Liste ganz einfach aufrufen. Alles, was uns interessiert, ist leer statt nicht leer.

Drittens, wie amalloy erklärt, der korrekte Wert von (cart) ist '(()). Das ist eigentlich eher subtil, und ich versehe das zuverlässig, wenn ich eine Funktion wie diese schreibe. Wenn Sie einen einfachen Fall sehr sorgfältig durchgehen, sollten Sie in der Lage sein zu sehen, warum dieser Wert die Rekursion funktioniert.

Viertens verwende ich im Allgemeinen nicht gerne fn. Dies ist eher eine persönliche Vorliebe, aber ich verwende immer #(), partial oder comp, wenn ich damit durchkommen kann. #() ist definitiv idiomatisch für kleinere Funktionen, obwohl die anderen beiden etwas weniger üblich sind.

Fünftens, einige Stilnoten. Das größte Problem ist der Einzug. Der beste Vorschlag ist hier, einen Editor zu finden, der Lisp-Code automatisch indentet. Auto-Indentation ist eines der wichtigsten Dinge, die Ihr Editor bereitstellen kann, da es blendend offensichtlich ist, wenn Ihre Parens nicht zusammenpassen. Auch schließende Parens gehen nie auf ihre eigene Linie, fn s brauchen keine internen Namen, es sei denn, Sie planen eine Rekursion, und ich habe generell ein paar mehr Zeilenumbrüche als Sie. Ich mag denken, dass mein Code oben einigermaßen anständig ist gestylt, und als ein weiteres Beispiel, hier ist, wie ich Ihren Code formatiert werden würde:

(defn cart 
    ([] '()) 
    ([l1] (map list l1)) 
    ([l1 l2] 
    (map (fn [x] 
      (map (fn [y] 
        (list x y)) 
       l2)) 
     l1))) 

(defn cartesian-product [& lists] 
    (reduce cart lists)) 

Answer 4

Ich würde https://github.com/clojure/math.combinatorics überprüft es hat

(Combo/kartesisch-Produkt [1 2] [3 4]) ;; => ((1 3) (1 4) (2 3) (2 4))

Answer 5

ich weiß, ich bin spät zum Party - ich will nur um der Vollständigkeit halber einen anderen Ansatz hinzuzufügen.

Im Vergleich zu amalloy Ansatz, ist es auch faul (die Parameterlisten werden jedoch eifrig ausgewertet) und etwas schneller, wenn alle Ergebnisse benötigt werden (Ich habe sie beide mit dem Demo-Code getestet), aber es ist anfällig für Stapelüberlauf (ähnlich wie das zugrunde liegende for Verständnis, das es generiert und auswertet), wenn die Anzahl der Listen zunimmt. Bedenken Sie auch, dass eval ein Limit für die Größe des Codes hat, an den es übergeben werden kann.

Betrachten sie zunächst eine einzelne Instanz des Problems: Sie wollen das kartesische Produkt von [:a :b :c] und '(1 2 3) zu finden. Die offensichtliche Lösung ist ein for Verständnis zu verwenden, wie folgt aus:

(for [e1 [:a :b :c] 
     e2 '(1 2 3)] 
    (list e1 e2)) 

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3)) 

Nun, die Frage ist: Ist es möglich, dies in einer Art und Weise zu verallgemeinern, die mit einer beliebigen Anzahl von Listen funktioniert? Die Antwort hier ist bejahend. Dies ist, was das folgende Makro tut:

(defmacro cart [& lists] 
    (let [syms (for [_ lists] (gensym))] 
    `(for [~@(mapcat list syms lists)] 
     (list ~@syms)))) 

(macroexpand-1 '(cart [:a :b :c] '(1 2 3))) 

; (clojure.core/for [G__4356 [:a :b :c] 
;     G__4357 (quote (1 2 3))] 
; (clojure.core/list G__4356 G__4357)) 

(cart [:a :b :c] '(1 2 3)) 

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3)) 

Im Wesentlichen haben Sie den Compiler das entsprechende for Verständnis für Sie generieren. Konvertieren dieser zu einer Funktion ist ziemlich einfach, aber es gibt einen kleinen Haken:

(defn cart [& lists] 
    (let [syms (for [_ lists] (gensym))] 
    (eval `(for [~@(mapcat #(list %1 `'~%2) syms lists)] 
      (list ~@syms))))) 

(cart [:a :b :c] '(1 2 3)) 

; ((:a 1) (:a 2) (:a 3) (:b 1) (:b 2) (:b 3) (:c 1) (:c 2) (:c 3)) 

Listen, die nicht notierten gelassen werden als Funktionsaufrufe behandelt, weshalb %2 zitiert hier notwendig ist.

Online Demo:

; https://projecteuler.net/problem=205 

(defn cart [& lists] 
    (let [syms (for [_ lists] (gensym))] 
    (eval `(for [~@(mapcat #(list %1 `'~%2) syms lists)] 
      (list ~@syms))))) 

(defn project-euler-205 [] 

    (let [rolls (fn [n d] 
       (->> (range 1 (inc d)) 
        (repeat n) 
        (apply cart) 
        (map #(apply + %)) 
        frequencies)) 

     peter-rolls (rolls 9 4) 
     colin-rolls (rolls 6 6) 

     all-results (* (apply + (vals peter-rolls)) 
         (apply + (vals colin-rolls))) 

     peter-wins (apply + (for [[pk pv] peter-rolls 
            [ck cv] colin-rolls 
            :when (> pk ck)] 
           (* pv cv)))] 

    (/ peter-wins all-results))) 

(println (project-euler-205)) ; 48679795/84934656 

Answer 6

Für die meisten Zwecke Alans Antwort ist groß, wie Sie ein faules Verständnis bekommen, und ein fauler seq nicht einen Stapelüberlauf verursachen, wie Sie seine Mitglieder erkennen, auch wenn Sie nicht verwenden (wiederkehren).

Ich war daran interessiert, den Schwanz rekursive Version mit expliziten recur Handwerk, nicht zuletzt von denen wegen Faulheit nicht los war keine Hilfe in meiner Anwendung sein, sondern auch für Spaß und kichert:

(defn cartesian-product 
    ([cols] (cartesian-product '([]) cols)) 
    ([samples cols] 
    (if (empty? cols) 
     samples 
     (recur (mapcat #(for [item (first cols)] 
         (conj % item)) samples) 
      (rest cols)))))