clojure functional-programming cartesian-product

Producto cartesiano en clojure



functional-programming cartesian-product (6)

Estoy tratando de implementar un método que tome una lista de listas y devuelva el producto cartesiano de estas listas.

Esto es lo que tengo hasta ahora:

(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))

El problema es que mi solución es en realidad ''salteada''.

(((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)))

Intenté agregar

(apply concat(reduce cart lists))

pero luego me da un choque como ese:

((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)

Por lo tanto, creo que estoy cerca, pero me falta algo. Sin embargo, dado que soy tan nuevo en programación y programación funcional, podría estar en la pista completamente equivocada. ¡Por favor ayuda! :)

En aras de la comparación, en el espíritu del original

(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))

Esto es mucho más fácil de hacer como una comprensión que tratando de resolver la recursión manualmente:

(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))

El caso base es obvio (debe ser una lista que contenga la lista vacía, no la lista vacía, ya que hay una forma de tomar un producto cartesiano sin listas). En el caso recursivo, simplemente itera sobre cada elemento x de la primera colección, y luego sobre cada producto cartesiano del resto de las listas, anteponiendo la x que ha elegido.

Para la mayoría de los propósitos, la respuesta de Alan es genial, ya que obtiene una comprensión perezosa, y un seq perezoso no causará un desbordamiento de la pila a medida que se da cuenta de sus miembros, incluso si no utiliza (recurre).

Me interesaba intentar crear la versión recursiva de la cola con recurrencia explícita, no menos importante porque la pereza no iba a ser de ninguna ayuda en mi aplicación, sino también para divertirme y reírme:

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

Personalmente, usaría amalloy for solución. Mi regla general es que si mi loop se puede expresar como un simple llamado map / filter / etc con un argumento de función simple (por lo tanto, un nombre de función o un formato corto fn / #() ), es mejor usar la función. Tan pronto como se vuelve más complejo que eso, una expresión for es mucho más fácil de leer. En particular, for es mucho mejor que los mapas anidados. Dicho esto, si no lo usara aquí, así es como escribiría la función:

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

Cosas a tener en cuenta: en primer lugar, no hay necesidad de reducir. Recursion puede manejarlo bien.

Segundo, solo dos casos. Podemos llamar a la función muy bien en una lista vacía, por lo que todo lo que nos importa es vacío vs no vacío.

En tercer lugar, como explicó amalloy, el valor correcto de (cart) es ''(()) . Esto es realmente bastante sutil, y lo arruino de manera confiable cuando escribo una función como esta. Si revisa cuidadosamente un caso simple, debería poder ver por qué ese valor hace que la recursión funcione.

En cuarto lugar, generalmente no me gusta usar fn . Esto es más una preferencia personal, pero siempre uso #() , partial o comp si puedo salirse con la suya. #() es definitivamente idiomático para funciones más pequeñas, aunque las otras dos son un poco menos comunes.

En quinto lugar, algunas notas de estilo. El mayor problema es la sangría. La mejor sugerencia es encontrar un editor que autoinduzca el código de ceceo. La sangría automática es una de las cosas más importantes que debe proporcionar su editor, ya que hace que sea obvio cuando sus pares no coinciden. Además, el cierre de parens nunca va por su propia cuenta, no necesita nombres internos a menos que esté pensando en recurrir, y generalmente tengo algunas líneas más nuevas que usted. Me gusta pensar que mi código anterior tiene un estilo razonablemente decente, y como otro ejemplo, así es como formatearé tu código:

(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))

Sé que llego tarde a la fiesta, solo quería agregar un enfoque diferente, en aras de la integridad.

Comparado con el enfoque de amalloy, también es perezoso (las listas de parámetros son evaluadas ansiosamente) y ligeramente más rápido cuando se requieren todos los resultados (los probé con el código de demostración a continuación), sin embargo, es propenso a desbordarse (al igual que subyacente for comprensión que genera y evalúa) a medida que aumenta la cantidad de listas. Además, tenga en cuenta que eval tiene un límite en el tamaño del código al que se puede pasar.

Considere primero una sola instancia del problema: desea encontrar el producto cartesiano de [:a :b :c] y ''(1 2 3) . La solución obvia es usar una for comprensión, como esta:

(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))

Ahora, la pregunta es: ¿es posible generalizar esto de una manera que funcione con un número arbitrario de listas? La respuesta aquí es afirmativa. Esto es lo que hace la siguiente macro:

(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))

Esencialmente, usted tiene el compilador que genera la comprensión adecuada para usted. Convertir esto en una función es bastante sencillo, pero hay un pequeño inconveniente:

(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))

Las listas que se dejan sin comillas se tratan como llamadas a funciones, por lo que aquí es necesario citar %2 .

Demostración en línea :

; 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