algorithm - unaria - Extracción de trayectorias de hoja del árbol n-aria en F#

relaciones unarias ejemplos

Question

Inspirado por esta pregunta , quería probar mi mano a la última reflexión sobre este desafío , usando F #

Mi enfoque probablemente esté completamente fuera de curso, pero en el curso de la solución de este problema, estoy tratando de obtener una lista de todas las permutaciones de los dígitos 0-9.

Estoy buscando resolverlo usando un árbol n-aria como ese:

type Node =
| Branch of (int * Node list)
| Leaf of int

Estoy bastante satisfecho de mí mismo, porque he logrado averiguar cómo generar el árbol que quiero.

Mi problema ahora es que no puedo descifrar cómo atravesar este árbol y extraer la ''ruta'' de cada hoja como un int. Lo que me confunde es que necesito unirme en nodos individuales, pero mi función ''externa'' debe tomar una lista de nodos.

Mi intento actual casi hace lo correcto, excepto que me devuelve la suma de todos los caminos ...

let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])])
let rec visitor lst acc =
let inner n =
match n with
| Leaf(h) -> acc * 10 + h
| Branch(h, t) -> visitor t (acc * 10 + h)
List.map inner lst |> List.sum
visitor [test] 0 //-> gives 633 (which is 321 + 312)

Y ni siquiera estoy seguro de que esto sea recursivo.

(Eres bienvenido para proponer otra solución para encontrar permutaciones, pero todavía estoy interesado en la solución a este problema en particular)

EDITAR: He publicado un algoritmo de permutaciones genéricas en F # aquí .

Answer 1

Con respecto a la pereza: puede hacer que esto sea flojo usando el tipo F # "seq" en lugar del tipo "list". Aquí hay un ejemplo:

let rec visitor2 lst tree =
match tree with
| Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub
| Leaf(n) ->
seq { do printfn "--yielding: %d" (lst * 10 + n)
yield lst * 10 + n };;

La cosa "seq" es una expresión de secuencia, que representa una secuencia de valores diferida. Agregué "printfn" al código, para que podamos rastrear cómo se están ejecutando las cosas:

> visitor2 0 tr |> Seq.take 2;;
--yielding: 13
--yielding: 124
val it : seq<int> = seq [13; 124]

Probablemente pueda usar algo como Seq.first para encontrar el primer valor que represente el resultado.

Answer 2

con respecto a su pregunta sobre el recorrido de la lista, puede comenzar escribiendo una función que devuelva listas que representen la ruta, creo que es más fácil y luego será más fácil convertirla en una función que devuelve un número.

Éste toma una lista como primer argumento (ruta hasta el momento) y un árbol y devuelve una lista> tipo: todas las rutas posibles desde la rama actual.

let rec visitor lst tree =
match tree with
| Branch(n, sub) -> List.collect (visitor (n::lst)) sub
| Leaf(n) -> [List.rev (n::lst)]
// For example...
> let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)] )]);;
> visitor [] tr;;
val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]]

En el caso ''Leaf'', simplemente agregamos el número actual a la lista y devolvemos el resultado como una lista que contiene una lista única (primero tenemos que revertirla, porque estábamos agregando números al comienzo). En el caso ''Rama'', agregamos ''n'' a la lista y recursivamente llamamos al visitante para que procese todos los subnodos de la rama actual. Esto devuelve un montón de listas y usamos ''map_concat'' para convertirlas en una sola lista que contiene todas las rutas posibles de la rama actual.

Ahora puede reescribir esto para devolver una lista de enteros:

let rec visitor2 lst tree =
match tree with
| Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub
| Leaf(n) -> [lst * 10 + n]
// For example...
> visitor2 0 tr;;
val it : int list = [13; 124; 125] 

En lugar de concatenar listas, ahora calculamos el número.