F#permutaciones

Question

Necesito generar permutaciones en una lista dada. Logré hacerlo así

let rec Permute (final, arr) = 
    if List.length arr > 0 then
        for x in arr do
            let n_final = final @ [x]
            let rest = arr |> List.filter (fun a -> not (x = a))
            Permute (n_final, rest)
    else
        printfn "%A" final

let DoPermute lst  = 
    Permute ([], lst)

DoPermute lst

Hay problemas obvios con este código. Por ejemplo, los elementos de la lista deben ser únicos. Además, este es más o menos el mismo enfoque que utilizaría al generar una implementación directa en cualquier otro idioma. ¿Hay alguna forma mejor de implementar esto en F #.

¡Gracias!

Answer 1

Depende de lo que quieras decir con "mejor". Considero que esto es un poco más elegante, pero eso puede ser una cuestión de gusto:

(* get the list of possible heads + remaining elements *)
let rec splitList = function
| [x] -> [x,[]]
| x::xs -> (x, xs) :: List.map (fun (y,l) -> y,x::l) (splitList xs)

let rec permutations = function
| [] -> [[]]
| l -> 
    splitList l 
    |> List.collect (fun (x,rest) ->
         (* permute remaining elements, then prepend head *)
         permutations rest |> List.map (fun l -> x::l))

Esto puede manejar listas con elementos duplicados, aunque dará como resultado permutaciones duplicadas.

Answer 2

Para las permutaciones de listas pequeñas, utilizo el siguiente código:

let distrib e L =
    let rec aux pre post = 
        seq {
            match post with
            | [] -> yield (L @ [e])
            | h::t -> yield (List.rev pre @ [e] @ post)
                      yield! aux (h::pre) t 
        }
    aux [] L

let rec perms = function 
    | [] -> Seq.singleton []
    | h::t -> Seq.collect (distrib h) (perms t)

Funciona de la siguiente manera: la función "distrib" distribuye un elemento dado sobre todas las posiciones en una lista, ejemplo:

distrib 10 [1;2;3] --> [[10;1;2;3];[1;10;2;3];[1;2;10;3];[1;2;3;10]]

La función perms funciona (recursivamente) de la siguiente manera: distribuya el encabezado de la lista sobre todas las permutaciones de su cola.

La función distrib será lenta para listas grandes, porque usa mucho el operador @, pero para listas de longitud razonable (<= 10), el código anterior funciona bien.

Una advertencia: si su lista contiene duplicados, el resultado contendrá permutaciones idénticas. Por ejemplo:

perms [1;1;3] = [[1;1;3]; [1;1;3]; [1;3;1]; [1;3;1]; [3;1;1]; [3;1;1]]

Lo bueno de este código es que devuelve una secuencia de permutaciones, en lugar de generarlas todas a la vez.

Por supuesto, generar permutaciones con un algoritmo basado en arreglos imperativos será (mucho) más rápido, pero este algoritmo me ha sido útil en la mayoría de los casos.

Answer 3

Aquí está la solución que di en mi libro F # para científicos (páginas 166-167):

let rec distribute e = function
  | [] -> [[e]]
  | x::xs'' as xs -> (e::xs)::[for xs in distribute e xs'' -> x::xs]

let rec permute = function
  | [] -> [[]]
  | e::xs -> List.collect (distribute e) (permute xs)

Answer 4

Aquí hay otra versión basada en secuencias, con suerte más legible que la respuesta. Esta versión es similar a la versión de Jon en términos de lógica, pero usa expresiones de cálculo en lugar de listas. La primera función calcula todas las formas de insertar un elemento x en una lista l. La segunda función calcula las permutaciones. Debería poder usar esto en listas más grandes (por ejemplo, para búsquedas de fuerza bruta en todas las permutaciones de un conjunto de entradas).

let rec inserts x l =
  seq { match l with
        | [] -> yield [x]
        | y::rest ->
            yield x::l
            for i in inserts x rest do
              yield y::i
      }

let rec permutations l =
  seq { match l with
        | [] -> yield []
        | x::rest ->
            for p in permutations rest do
              yield! inserts x p
      }

Answer 5

En mi humilde opinión, la mejor solución debería aliviar el hecho de que F # es un lenguaje funcional, de modo que la solución debería ser lo más cercana posible a la definición de lo que queremos decir como permutación. Entonces, la permutación es una instancia de lista de cosas en la que el encabezado de la lista se agrega de alguna manera a la permutación del resto de la lista de entrada. La solución de Erlang muestra eso de una manera bonita:

permutations([]) -> [[]];
permutations(L) -> [[H|T] H<- L, T <- permutations( L--[H] ) ].

tomado del libro "programación erlang"

Hay un operador de comprensión de listas utilizado, en la solución mencionada aquí por los compañeros ers hay una función auxiliar que hace el trabajo similar, básicamente votaría por la solución sin bucles visibles, etc., simplemente la definición de la función pura

Answer 6

En el espíritu de la sugerencia de Cyrl, aquí hay una versión de comprensión de secuencia

let rec permsOf xs =
  match xs with
  | [] -> List.toSeq([[]])
  | _ -> seq{ for x in xs do
               for xs'' in permsOf (remove x xs) do
                 yield (x::xs'')}

donde remove es una función simple que elimina un elemento dado de una lista

let rec remove x xs =
  match xs with [] -> [] | (x''::xs'')-> if x=x'' then xs'' else x''::(remove x xs'')