Generar todas las permutaciones en Clojure -- beginner campo con functional-programming campo con combinatorics campo con clojure camp codereview Relacionados El problema

Generate all permutations in Clojure


2
vote

problema

Español

Dado un conjunto, genera todas las permutaciones:

  class application {      String productID;      String customerID;      String applicationId;      String name;  ....   // getters and setters and associated constructors }  class product {     String name;     String ID;     ...   // constructors and getters and setters  }  class customer {     String name;     String ID;     ...     // constructors and getters and setters } 1  

Aquí está lo que me diagmenté:

  class application {      String productID;      String customerID;      String applicationId;      String name;  ....   // getters and setters and associated constructors }  class product {     String name;     String ID;     ...   // constructors and getters and setters  }  class customer {     String name;     String ID;     ...     // constructors and getters and setters } 2  

Pensé que mi solución era horrible, así que fui a buscar otras soluciones y encontré este :

  class application {      String productID;      String customerID;      String applicationId;      String name;  ....   // getters and setters and associated constructors }  class product {     String name;     String ID;     ...   // constructors and getters and setters  }  class customer {     String name;     String ID;     ...     // constructors and getters and setters } 3  

¡Se ve tan elegante! No estoy acostumbrado a la programación funcional, así que encuentro que el flujo de ejecución es inmensamente difícil de seguir. En particular, no entiendo lo que está siendo concatinado. ¿Es el resultado de la primera llamada class application { String productID; String customerID; String applicationId; String name; .... // getters and setters and associated constructors } class product { String name; String ID; ... // constructors and getters and setters } class customer { String name; String ID; ... // constructors and getters and setters } 4

¿Algún consejo para mejorar mi proceso de pensamiento para que pueda encontrar una solución como esa por mi cuenta? Estoy acostumbrado a programar imperativamente y no encuentro funciones como class application { String productID; String customerID; String applicationId; String name; .... // getters and setters and associated constructors } class product { String name; String ID; ... // constructors and getters and setters } class customer { String name; String ID; ... // constructors and getters and setters } 5 o class application { String productID; String customerID; String applicationId; String name; .... // getters and setters and associated constructors } class product { String name; String ID; ... // constructors and getters and setters } class customer { String name; String ID; ... // constructors and getters and setters } 6 intuitive. ¿Hay alguna manera de hacer que esta función sea más legible o lo mejore más de otras maneras?

Original en ingles

Given a set, generate all permutations:

(permutations #{1 4 5}) => ((5 4 1) (4 5 1) (5 1 4) (1 5 4) (4 1 5) (1 4 5)) 

Here's what I cobbled together:

(defn perm-r [allPerms currentPerm input i]   (cond     (empty? input) (conj allPerms currentPerm)     (< i 0) allPerms     :else (perm-r             (perm-r               allPerms               (conj currentPerm (nth input i))               (remove (fn [x] (= x (nth input i))) input)               (dec                 (count                   (remove                     (fn [x] (= x (nth input i)))                     input))))             currentPerm             input             (dec i))))  (defn permutations [a-set]   (perm-r `() `() (seq a-set) (dec (count a-set)))) 

I thought my solution was awful, so I went to look for other solutions and found this:

(defn rotations [a-seq]   (distinct (map concat (tails a-seq) (inits a-seq))))  (defn permutations [a-set]   (if (empty? a-set)     (list ())     (apply concat (map (fn [x] (map cons (repeat (first x))                                          (permutations (rest x))))                   (rotations a-set))))) 

It looks so elegant! I'm not used to functional programming, so I find the execution flow immensely difficult to follow. In particular, I don't understand what's being concatenated. Is the result of the first map call (which represents what exactly?) to every rotation of a-set?

Any tips on improving my thought process so that I could come up with a solution like that on my own? I'm used to programming imperatively and I don't find functions like map or apply intuitive. Is there a way to make this function more readable or improve it further in other ways?

           
 
 

Lista de respuestas

5
 
vote
vote
La mejor respuesta
 

Limpiemos un poco el código.

FUNCIÓN black1 Nos da todas las posibles subsecuencias de finalización. Por ejemplo ...

  black2  

y black3 Nos da todas las subsecuencias iniciales. Por ejemplo ...

  black4  

Para obtener las rotaciones, nos casamos con el black5 con el 99887766555443326 black7 . Si solo nosotros

  black8  

` ... Luego obtenemos la secuencia original en ambos extremos:

  black9  

El código dado utiliza TKINTER SCRIPT0 para deshacerse del duplicado. Es más rápido y sencillo usar TKINTER SCRIPT1 :

  TKINTER SCRIPT2  

ahora

  TKINTER SCRIPT3  

y estamos listos para generar todas las permutaciones. Podemos reescribir el código dado de la siguiente manera:

  TKINTER SCRIPT4  
  • TKINTER SCRIPT55 es una abreviatura para TKINTER SCRIPT6 .
  • TKINTER SCRIPT7 es un formulario que establece TKINTER SCRIPT8 a la TKINTER SCRIPT9 y pathlib0 al pathlib1 de su argumento de secuencia.
  • pathlib2 es una abreviatura para pathlib3 , A Función que pone pathlib4 en la parte frontal de su argumento de secuencia.

Para cada rotación del conjunto dado, el pathlib55 se pega su primer elemento en cada permutación del resto de los elementos, y luego concatena todas estas colecciones. Por ejemplo ...

  pathlib6  

Eso es todo.


El 99887766554443347

  pathlib8  

... es un poco excesivo en exceso, debido a todo el pathlib9 s. Una forma más amable de obtener el script_directory+"/mycsv.csv 0 es

  script_directory+"/mycsv.csv 1  

 

Let's clean the code up a bit.

Function tails gives us all the possible ending sub-sequences. For example ...

(tails (range 3)) ; ((0 1 2) (1 2) (2) ()) 

And inits gives us all the initial sub-sequences. For example ...

(inits (range 3)) ; (() (0) (0 1) (0 1 2)) 

To get the rotations, we marry the init with the corresponding tail,using concat. If we just

(defn rotations [a-seq]   (map concat (tails a-seq) (inits a-seq))) 

` ... then we get the original sequence at both ends:

(rotations (range 5)) ; ((0 1 2 3 4) (1 2 3 4 0) (2 3 4 0 1) (3 4 0 1 2) (4 0 1 2 3) (0 1 2 3 4)) 

The given code uses distinct to get rid of the duplicate. It's faster and simpler to use rest:

(defn rotations [a-seq]   (rest (map concat (tails a-seq) (inits a-seq)))) 

Now

(rotations (range 5)) ; ((1 2 3 4 0) (2 3 4 0 1) (3 4 0 1 2) (4 0 1 2 3) (0 1 2 3 4)) 

And we're ready to generate all the permutations. We can rewrite the given code as follows:

(defn permutations [a-set]   (if (empty? a-set)     (list ())     (mapcat      (fn [[x & xs]] (map #(cons x %) (permutations xs)))      (rotations a-set)))) 
  • (mapcat f coll)is an abbreviation for (apply concat (map f coll)).
  • (fn [[x & xs]] ... ) is a destructuring form that sets x to the first and xs to the rest of its sequence argument.
  • #(cons x %) is an abbreviation for (fn [y] (cons x y)), a function that puts x on the front of its sequence argument.

For every rotation of the given set, the permutations function glues its first element onto each permutation of the rest of the elements, and then concatenates all these collections together. For example ...

(permutations (range 3)) ; ((1 0 2) (1 2 0) (2 1 0) (2 0 1) (0 2 1) (0 1 2)) 

That's it.


The given inits ...

(defn inits [a-seq]   (reverse (map reverse (tails (reverse a-seq))))) 

... is somewhat overworked, on account of all the reverses. A neater way to get the rotations is

(defn rotations [a-seq]   (let [a-vec (vec a-seq)]     (for [i (range (count a-vec))]       (concat (subvec a-vec i) (subvec a-vec 0 i))))) 
 
 
     
     

Relacionados problema

11  ¿Es esta la forma en ello a Web-Scrape a una imagen de portada de libros?  ( Is this the clojure way to web scrape a book cover image ) 
¿Hay una manera de escribir esto mejor o más de manera de engaño? Especialmente la última parte con with-open y el let . ¿Debo poner el formulario 9988776...

4  Envoltura API para Clojure  ( Api wrapper for clojure ) 
Quería envolver el biblioteca JeyMaster en una envoltura de Clojure (para mi propio uso, pero tal vez también para salvar a otros algún tiempo). Solo estoy ...

25  Proyecto EULER PROBLEMA 2 EN COTJURE  ( Project euler problem 2 in clojure ) 
Estoy en el proceso de aprendizaje de Clojure. Soy bastante nuevo en la programación funcional y me gustaría saber si mi código huele o si hay alguna implicac...

1  Barajando muchas colecciones doblando sobre una gama numérica  ( Shuffling many collections by folding over a numeric range ) 
a menudo, me encuentro plegando sobre un objeto range si necesito transformar algo repetidamente. Esto, para mí, sin embargo, se siente como un abuso de fo...

1  Ejercicio: limpiar y formatear un número de teléfono en Clojure  ( Exercism clean and format a phone number in clojure ) 
Declaración de problemas Número de teléfono Escriba un programa que limpie los números de teléfono ingresados ​​por el usuario para que puedan ser envi...

13  Muestreo de reservorio en Clojure  ( Reservoir sampling in clojure ) 
Estoy aprendiendo a Clojure y decidí comenzar por intentar escribir una solución a un algoritmo bastante simple, un muestreo de reservorio. Como dije, estoy a...

7  Cuerdas de partición en subcadenas de longitud fija  ( Partitioning strings into substrings of fixed length ) 
Tengo una función de Clojure aquí que está destinado a analizar una cadena de forma: "ddxxxyyy" Donde DD está destinado a ser descartado, y XXX y YYY so...

4  Encuentre los caracteres comunes entre dos cuerdas sin usar las operaciones establecidas  ( Find the common characters between two strings without using set operations ) 
A continuación se presentan dos implementaciones del problema "Encuentre los caracteres en común entre dos cadenas": en Clojure sin utilizar las operaciones d...

5  Fórmula Haversine en Clojure  ( Haversine formula in clojure ) 
Implementé el fórmula haversine para calcular la distancia entre dos (latitud , longitud) coordenadas. Me preguntaba si se ve natural para los programador...

2  Resolviendo la ecuación cuadrática en Clojure  ( Solving quadratic equation in clojure ) 
Escribí una función en Clojure para resolver ecuaciones cuadráticas utilizando la fórmula cuadrática la función (defn solvequadeq [a b c] (let [D (-...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos