Permessi F #

Question

Ho bisogno di generare permutazioni su una lista data. Sono riuscito a farlo in questo modo

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 

Ci sono ovvi problemi con questo codice. Ad esempio, gli elementi della lista devono essere unici. Inoltre, questo è più o meno lo stesso approccio che userei per generare un'implementazione diretta in qualsiasi altra lingua. C'è un modo migliore per implementarlo in F #.

Grazie!

Answer 1

Per permutazioni di piccole liste, ho utilizzare il seguente codice:

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) 

Funziona come segue: il "distrib" funzione distribuisce un dato elemento su tutte le posizioni in un elenco, ad esempio:

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

La funzione funzioni funziona (in modo ricorsivo) come segue: distribuire il capo dell'elenco su tutte le permutazioni della coda.

La funzione di distribuzione rallenta per le liste di grandi dimensioni, poiché utilizza molto l'operatore @, ma per gli elenchi di lunghezza ragionevole (< = 10), il codice sopra funziona correttamente.

Un avvertimento: se l'elenco contiene duplicati, il risultato conterrà permute identiche. Per esempio:

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

La cosa bella di questo codice è che restituisce una sequenza di permutazioni, invece di generare tutti in una volta.

Ovviamente, la generazione di permutazioni con un algoritmo imperativo basato su array sarà (molto) più veloce, ma questo algoritmo mi ha servito bene nella maggior parte dei casi.

Answer 2

Dipende da cosa intendi per "migliore". Mi piacerebbe prendere in considerazione questo per essere un po 'più elegante, ma che può essere una questione di 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)) 

Questo in grado di gestire liste con elementi duplicati, anche se il risultato sarà permutazioni duplicati.

Answer 3

Ecco la soluzione che ho dato nel mio libro F# for Scientists (pag 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

Ecco un'altra versione sequenza-based, si spera più leggibile la risposta votato. Questa versione è simile alla versione di Jon in termini di logica, ma utilizza espressioni di calcolo anziché elenchi. La prima funzione calcola tutti i modi per inserire un elemento x in una lista l. La seconda funzione calcola le permutazioni. Dovresti essere in grado di usarlo su elenchi più grandi (ad esempio per ricerche di forza bruta su tutte le permutazioni di un insieme di input).

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

IMHO la soluzione migliore dovrebbe alleviare il fatto che F # è un linguaggio funzionale in modo IMHO la soluzione deve essere il più vicino alla definizione di ciò che intendiamo come permutazione là possibile. Quindi la permutazione è una tale istanza di lista di cose in cui la testa della lista è in qualche modo aggiunta alla permutazione del resto della lista di input. La soluzione Erlang dimostra che in un modo piuttosto:

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

preso fron il "Erlang programmazione" libro

V'è un operatore di lista utilizzata, in soluzione qui menzionato dal borsista stackoverflowers c'è un aiutante funzione che fa il lavoro simile fondamentalmente mi piacerebbe votare per la soluzione senza alcun loop visibili ecc, basta definizione di funzione pura

Answer 6

Nello spirito del suggerimento di Cyrl, ecco una versione sequenza di comprensione

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')} 

dove remove è una semplice funzione che rimuove un dato elemento da un elenco

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