Crear lista de caminos tomados

2
phoxd 2019-08-29 05:54.

Dado el rango (a,b)y las líneas (x,y), quiero construir todas las formas posibles de cubrir el rango con las líneas dadas.

Por ejemplo, con el rango (0,10)(si filtramos la lista para que esté dentro del rango, entonces no tenemos que preocuparnos por eso) y la siguiente lista (ordenarla facilita la elección del siguiente valor),

list = [(0,1), (1,10), (1,4), (3,5), (5,10)]

Quiero generar una lista de rutas tomadas para cubrir el rango de la siguiente manera,

[
[(0,1), (1,4), (3,5), (5,10)],
[(0,1), (1,10)]
]

Intenté configurar la función que obtendría la lista de los siguientes (x,y)valores posibles de la siguiente manera, pero solo imprime una única ruta.

-- assume list is sorted based on first pair
nextpaths :: (Num a, Ord a) => [(a, a)] -> ([(a, a)], [(a, a)])
nextpaths ((start, end):xs) = go xs ([], [])
  where go [] acc = acc
        go (y:ys) (next, rest)| fst y <= end = go ys (y:next, rest)
                              | otherwise = (next, y:ys)

paths [email protected](x:xs) = case nextpaths t of
  ([],_) -> [[x]]
  (n:next, rest) -> map (x:) (paths (n:rest))

¿Cómo haríamos que las pathsfunciones se apliquen a otros nextvalores de lista?

2 answers

2
Willem Van Onsem 2019-09-02 02:17.

Podemos generar una lista de rutas mínimas : rutas en las que no podemos eliminar una sola tupla 2 de modo que siga siendo una ruta válida.

Por lo general, aquí es más eficiente trabajar con una lista ordenada de fragmentos, ya que podemos escanear la lista y agregar elementos que sean necesarios. Cuando escaneamos, necesitaremos dos cosas: el rango que queremos cubrir; y la última gama, de tal forma que garantizamos la minimidad.

Primero construiremos una función donde asumimos que ya seleccionamos una ruta. Así podemos definir una función con firma:

paths1 :: Ord a => (a, a) -> (a, a) -> [(a, a)] -> [[(a, a)]]

En caso de que el último elemento seleccionado sea mayor o igual que el límite superior del rango, hemos terminado. En ese caso, devolvemos una lista singleton con una lista vacía. La llamada recursiva puede agregar la subruta seleccionada a la lista:

paths1 (a, f) (b, c) _ | c >= f = [[]]

En caso de que se agote la lista de posibles subrangos, no podemos generar dicha ruta, por lo que devolvemos una lista vacía en caso de que la lista de subrangos esté vacía:

paths1 _ _ [] = []

En caso de que aún no hayamos llegado al final, necesitaremos un subrango adicional. Dicho subrango debe satisfacer dos criterios: debe comenzar después del subtrayecto seleccionado previamente y debe terminar después del subtrayecto seleccionado previamente. Por tanto, podemos saltarnos suranges que no satisfagan esa condición:

paths1 r [email protected](b, c) ((d, e):xs) | d > c = []
                              | d <= b || e <= c = paths1 r s xs

En caso de que podamos seleccionar el subrango, podemos elegir ese. En ese caso, actualizamos el último rango seleccionado y anteponemos todas las rutas que se devuelven:

paths1 r [email protected](_,sb) ([email protected](_, xb):xs) = map (x:) (paths1 r (sb,xb) xs) ++ paths1 r s xs

Ahora hemos definido una implementación completa para paths1:

paths1 :: Ord a => (a, a) -> (a, a) -> [(a, a)] -> [[(a, a)]]
paths1 (a, f) (b, c) _ | c >= f = [[]]
paths1 _ _ [] = []
paths1 r [email protected](b, c) ((d, e):xs) | d > c = []
                              | d <= b || e <= c = paths1 r s xs
paths1 r [email protected](_,sb) ([email protected](_, xb):xs) = map (x:) (paths1 r (sb,xb) xs) ++ paths1 r s xs

Ahora necesitamos implementar una función que seleccione el primer subrango. Podemos implementar dicha función path0:

paths0 :: (a, a) -> [(a, a)] -> [[(a, a)]]

El primer rango que deberíamos seleccionar debe comenzar antes del inicio del rango que queremos generar y después del inicio del rango. Por lo tanto, podemos implementar eso como:

paths0 :: Ord a => (a, a) -> [(a, a)] -> [[(a, a)]]
paths0 (a, _) ((b, c):_) | b > a || c <= a = []
paths0 [email protected](a, _) ((_, c):xs) | c <= a = paths0 r xs
paths0 r (x:xs) = map (x:) (paths1 r x xs) ++ paths0 r xs

Entonces ahora podemos combinar los dos en una pathfunción. Primero podemos ordenar la lista o agregar esto como una condición previa:

import Data.List(sort)

paths :: (a, a) -> [(a, a)] -> [[(a, a)]]
paths = (. sort) . paths0

Luego obtenemos el resultado esperado:

Prelude Data.List> paths (0,10) [(0,1), (1,10), (1,4), (3,5), (5,10)]
[[(0,1),(1,4),(3,5),(5,10)],[(0,1),(1,10)]]

Lo anterior no es la solución más elegante. Dejo " pulirlo " más como ejercicio.

3
Ignat Insarov 2019-09-08 17:07.

En realidad, este es un problema de cierta profundidad.

O, mejor dicho, el algoritmo que solicita es simple (si se lo aborda con las herramientas adecuadas a mano) ; pero comprobar si es correcto no lo es, y es muy fácil cometer un pequeño error. Esto se debe a que los intervalos se diferencian de los números en el sentido de que ya no existe una noción tan simple como el orden total habitual, y las relaciones que tenemos son diez veces más complejas, demasiado lejos para que las capte la mente humana desarmada.

Por tanto, ¿cuáles deberían ser nuestras metas?

  1. Necesitamos entender cómo se relacionan los intervalos entre sí.
  2. Necesitamos poder comprobar si un determinado conjunto de intervalos es una solución al problema.

En este escrito, diré "base" que significa el intervalo a cubrir, y "cadena" que consiste en "eslabones" que significa un conjunto de intervalos que pueden estar cubriendo. (Eventualmente justificaré este último nombre).

Así que armémonos.

Con números (es decir, puntos únicos) , solo hay 3 relaciones cualitativas disjuntas: a < bo a = bo a > b. Entonces, ¿ qué podemos decir acerca de los pares de números (que representan intervalos) ? Hay 5 lugares en los que puede estar un punto con respecto a un intervalo:

             on the left end
             v
-- before -- * == inside == * -- after --
                            ^
                            on the right end

Considerando que el extremo izquierdo de un intervalo nunca está a la derecha de su extremo derecho (duh) , esto nos da sum [5, 4.. 1] = 15relaciones cualitativas inconexas entre dos intervalos. Sin tener en cuenta las dos relaciones donde ambos extremos de un intervalo están en el mismo extremo del otro (lo que significa que el intervalo es un punto) , da 13. Y ahora hay una técnica anterior que discute exactamente 13 relaciones exhaustivas disjuntas sobre intervalos. ( Artículo original. )

Es decir, se definen estas 6 relaciones:

precedes      =  \ i j  ->  right i < left j
meets         =  \ i j  ->  right i == left j && left i /= left j && right i /= right j
overlaps      =  \ i j  ->  left i < left j  && right i < right j && right i > left j
isFinishedBy  =  \ i j  ->  left i < left j  && right i == right j
contains      =  \ i j  ->  left i < left j  && right i > right j
starts        =  \ i j  ->  left i == left j && right i < right j

- Junto con sus inversiones flip ...y la relación de igualdad.

Mientras que para los números podemos derivar exactamente 8 relaciones compuestas en términos de las 3 básicas (considerando las relaciones como un espacio vectorial sobre el campo binario) , en intervalos podemos definir alrededor de 8 mil . Algunos de ellos nos serán de utilidad dentro de este problema:

absorbs         =  isFinishedBy `or` contains `or` flip starts `or` (==)
isDisjointWith  =  precedes     `or` flip precedes
joins           =  (fmap . fmap) not isDisjointWith
touches         =  meets        `or` overlaps
isRightwardsOf  =  flip (precedes `or` touches)
...

Dadas estas relaciones, podemos manipularlas para obtener todo tipo de dispositivos increíbles, como cierres, equivalencias y órdenes. En la actualidad utilizaré algunos para obtener un verificador de soluciones a nuestro problema.

  1. Un cierre reflexivo, simétrico y transitivo de joinses una equivalencia bajo la cual se consideran equivalentes aquellos intervalos que pertenecen a una línea contigua. (Aunque no es necesariamente adyacente en esa línea).
  2. Un conjunto normal de intervalos es aquel en el que todos los intervalos están separados.
    • Cualquier conjunto puede normalizarse uniendo los intervalos que se unen hasta que no quede ninguno.
    • La normalización conserva la cobertura: exactamente cuando un punto pertenece a algunos de los intervalos de un conjunto, pertenecerá a algún intervalo en su normalización.
  3. Una solución es una cadena tal que:
    • Su normalización es un conjunto singleton cuyo único miembro es absorbsla base. (Suficiente.)
    • Con cualquier enlace eliminado, esta condición ya no se mantiene. (Mínimo.)

Por lo tanto, normalizees una función que divide un conjunto de intervalos en clases de equivalencia inducida por joinsy convierte cada clase en un intervalo tomando los extremos de todos los puntos finales.

relation :: Ord a => Set a -> (a -> a -> Bool) -> Relation a

closure :: Relation a -> Relation a

classifyBy :: Ord a => (a -> a -> Bool) -> Set a -> Set (Set a)

(?) :: Eq a => Relation a -> (a, a) -> Bool

bounds :: Ord a => Set a -> Interval a

flatten :: Ord a => Set (Interval a) -> Set a

normalize :: Ord a => Set (Interval a) -> Set (Interval a)
normalize u | Set.null u = Set.empty
            | otherwise = let  rel = closure (relation u joins)
                               classes = classifyBy (curry (rel ?)) u
                          in Set.map (bounds . flatten) classes

En estos términos, podemos definir el cheque:

isCovering :: Ord a => Interval a -> [Interval a] -> Bool
isCovering base xs = case (Set.toList . normalize . Set.fromList) xs of
                        [y] -> y `absorbs` base
                        _   -> False

isMinimalCovering :: Ord a => Interval a -> [Interval a] -> Bool
isMinimalCovering base xs = sufficient && minimal
    where sufficient = isCovering base xs
          minimal    = List.null . filter (isCovering base)
                                 . fmap (`deleteAt` xs) $ [0.. length xs - 1]

No solo eso, podemos definir un filtro:

bruteForceCoveringChains :: forall a. (Ord a, Num a)
                         => Interval a -> [Interval a] -> [[Interval a]]
bruteForceCoveringChains base xs = filter (isMinimalCovering base) (List.subsequences xs)

La complejidad temporal de estos dispositivos es una locura. Empíricamente, esta solución de fuerza bruta puede atravesar un conjunto de 10 intervalos, pero no 20. Pero esto es suficiente para comparar un algoritmo rápido candidato.

¡Adelante ahora!

Todos los eslabones de nuestra cadena deben conectarse, como ... eslabones de una cadena. Uno después del otro. Hay una relación para eso: el que nombré touches. Si una serie de intervalos se tocan consecutivamente, tenemos la certeza de que cubren el espacio desde el inicio del primero hasta el final del último. Podemos usar esta relación para filtrar consecutivamente más y más eslabones en nuestra cadena hasta que subsume la base por completo.

Dicho touchessea ​​de paso, es una relación antisimétrica, lo que hace de su cierre transitivo y reflexivo un ordenamiento de intervalos, y una teoría de la cadena en orden es exactamente un conjunto totalmente ordenado. Entonces, nuestra denominación está justificada: hay una relación que no es un ordenamiento total para conjuntos arbitrarios de intervalos, sino un ordenamiento total para nuestras cadenas.

Sin embargo, esto no es suficiente: también debemos asegurarnos de que nuestra cadena sea mínima. Afirmo que esta condición se cumple exactamente cuando notouches hay ninguna parte transitiva en nuestra cadena. Eso quiere decir: cuando x `touches` yy y `touches` z, nunca es eso x `touches` z (de lo contrario, no lo necesitaríamos yen nuestra cadena) . Observe que, al igual que los eslabones de una cadena real, nuestros "eslabones" solo deben superponerse de dos en dos. Este requisito puede parafrasearse en términos de relaciones de intervalo: un vínculo debe ser tocado por el intervalo entre el final del vínculo anterior y el anterior al anterior. Suena un poco barroco, pero estoy seguro de que el lector podrá plasmar esta situación en su mente o en un papel.

Y esto es todo lo que se necesita para dar una definición recursiva que estamos buscando.

chainsFromTo :: Ord a => Interval a -> Interval a -> [Interval a] -> [[Interval a]]
chainsFromTo start end xs' = case base of
    Point _ -> (fmap pure . filter (`absorbs` base)) xs'
    _       -> baseCase ++ recursiveCase
  where
    base = right start ~~ left end

    xs = filter (not . isDisjointWith base) xs'

    baseCase = do
        x <- filter ((start `touches`) * (`touches` end)) xs
        return [x]

    recursiveCase = do
        x <- filter ((start `touches`) * not . (`touches` end)) xs
        xs <- chainsFromTo (right start ~~ right x) end (filter (`isRightwardsOf` x) xs)
        return $ x: xs

coveringChainsFromTo :: forall a. (Ord a, Num a)
                     => Interval a -> [Interval a] -> [[Interval a]]
coveringChainsFromTo _   [ ] = [ ]
coveringChainsFromTo base xs = chainsFromTo start end xs
  where
    start = (\z -> z - 1) (left reach) ~~ left base
    end = right base ~~ (\z -> z + 1) (right reach)
    reach = (bounds . flatten . Set.fromList) xs

Una vez que lo tienes, parece sencillo, pero intenté como una docena de veces hacerlo bien, y solo una verificación exhaustiva me ayudó a localizar y arreglar todos los casos de esquina. Puedes ver el código completo en un repositorio .

Eso es.

Espero que ayude. Comente si mi presentación no es clara o si me perdí algo.

Related questions

MORE COOL STUFF

La estrella de HGTV, Christina Hall, revela que tiene 'envenenamiento por mercurio y plomo' probablemente por voltear 'casas asquerosas'

La estrella de HGTV, Christina Hall, revela que tiene 'envenenamiento por mercurio y plomo' probablemente por voltear 'casas asquerosas'

La estrella de HGTV, Christina Hall, revela que le diagnosticaron envenenamiento por mercurio y plomo, probablemente debido a su trabajo como manipuladora de casas.

La estrella de 'Love Is Blind' Brennon Lemieux responde a los cargos de violencia doméstica

La estrella de 'Love Is Blind' Brennon Lemieux responde a los cargos de violencia doméstica

Recientemente salió a la luz un informe policial que acusa a la estrella de 'Love Is Blind', Brennon, de violencia doméstica. Ahora, Brennon ha respondido a los reclamos.

Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia Judd en un momento festivo de pánico

Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia Judd en un momento festivo de pánico

Conozca cómo Wynonna Judd se dio cuenta de que ahora es la matriarca de la familia mientras organizaba la primera celebración de Acción de Gracias desde que murió su madre, Naomi Judd.

Experto en lenguaje corporal explica los 'paralelos' entre Kate Middleton y la princesa Diana

Experto en lenguaje corporal explica los 'paralelos' entre Kate Middleton y la princesa Diana

Descubra por qué un destacado experto en lenguaje corporal cree que es fácil trazar "tales paralelismos" entre la princesa Kate Middleton y la princesa Diana.

Los láseres arrojan luz sobre por qué necesita cerrar la tapa antes de descargar

Los láseres arrojan luz sobre por qué necesita cerrar la tapa antes de descargar

Los inodoros arrojan columnas de aerosol invisibles con cada descarga. ¿Como sabemos? La prueba fue capturada por láseres de alta potencia.

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

¿Caduca el repelente de insectos?

¿Caduca el repelente de insectos?

¿Sigue siendo efectivo ese lote de repelente de insectos que te quedó del verano pasado? Si es así, ¿por cuánto tiempo?

Ponle una tapa. En realidad, ponle una tapa a todo. Consigue 12 tapas de cocina elásticas de silicona por $14. [Exclusivo]

Ponle una tapa. En realidad, ponle una tapa a todo. Consigue 12 tapas de cocina elásticas de silicona por $14. [Exclusivo]

Tapas elásticas de silicona de Tomorrow's Kitchen, paquete de 12 | $14 | Amazonas | Código promocional 20OFFKINJALids son básicamente los calcetines de la cocina; siempre perdiéndose, dejando contenedores huérfanos que nunca podrán volver a cerrarse. Pero, ¿y si sus tapas pudieran estirarse y adaptarse a todos los recipientes, ollas, sartenes e incluso frutas en rodajas grandes que sobran? Nunca más tendrás que preocuparte por perder esa tapa tan específica.

Cuéntanos tus mejores trucos de Washington, DC

Cuéntanos tus mejores trucos de Washington, DC

Hemos pirateado algunas ciudades industriales en esta columna, como Los Ángeles y Las Vegas. Ahora es el momento de una ciudad militar-industrial-compleja.

Un minorista está eliminando su sección de tallas grandes y mezclando tallas más grandes con todo lo demás

Un minorista está eliminando su sección de tallas grandes y mezclando tallas más grandes con todo lo demás

Un minorista está enlatando su sección de tallas grandes. Pero no están tomando la categoría solo en línea o descontinuándola por completo.

La mejor forma de guardar animales de peluche es dentro de un puf

La mejor forma de guardar animales de peluche es dentro de un puf

Entiendo totalmente, completamente si tienes una relación difícil con los animales de peluche. Son lindos, tienen valor sentimental y es difícil separarse de ellos.

Patinaje artístico de EE. UU. 'frustrado' por falta de decisión final en evento por equipos, pide una decisión justa

Patinaje artístico de EE. UU. 'frustrado' por falta de decisión final en evento por equipos, pide una decisión justa

El equipo está a la espera de las medallas que ganó en los Juegos Olímpicos de Invierno de 2022 en Beijing, ya que se está resolviendo un caso de dopaje que involucra a la patinadora artística rusa Kamila Valieva.

Los compradores de Amazon dicen que duermen 'como un bebé mimado' gracias a estas fundas de almohada de seda que cuestan tan solo $ 10

Los compradores de Amazon dicen que duermen 'como un bebé mimado' gracias a estas fundas de almohada de seda que cuestan tan solo $ 10

Miles de compradores de Amazon recomiendan la funda de almohada de seda Mulberry, y está a la venta en este momento. La funda de almohada de seda viene en varios colores y ayuda a mantener el cabello suave y la piel clara. Compre las fundas de almohada de seda mientras tienen hasta un 46 por ciento de descuento en Amazon

Se busca al corredor de los Bengals Joe Mixon por orden de arresto emitida por presuntamente apuntar con un arma de fuego a una mujer

Se busca al corredor de los Bengals Joe Mixon por orden de arresto emitida por presuntamente apuntar con un arma de fuego a una mujer

El jueves se presentó una denuncia de delito menor amenazante agravado contra Joe Mixon.

Profesor de la Universidad de Purdue arrestado por presuntamente traficar metanfetamina y proponer favores sexuales a mujeres

Profesor de la Universidad de Purdue arrestado por presuntamente traficar metanfetamina y proponer favores sexuales a mujeres

El Departamento de Policía de Lafayette comenzó a investigar a un profesor de la Universidad de Purdue en diciembre después de recibir varias denuncias de un "hombre sospechoso que se acercaba a una mujer".

Concept Drift: el mundo está cambiando demasiado rápido para la IA

Concept Drift: el mundo está cambiando demasiado rápido para la IA

Al igual que el mundo que nos rodea, el lenguaje siempre está cambiando. Mientras que en eras anteriores los cambios en el idioma ocurrían durante años o incluso décadas, ahora pueden ocurrir en cuestión de días o incluso horas.

India me está pateando el culo

India me está pateando el culo

Estoy de vuelta por primera vez en seis años. No puedo decirte cuánto tiempo he estado esperando esto.

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language