F # перестановки

Question

Мне нужно сгенерировать перестановки в заданном списке. Мне удалось это сделать

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 

С этим кодом очевидны проблемы. Например, элементы списка должны быть уникальными. Кроме того, это более-менее такой же подход, который я бы использовал при создании прямой реализации на любом другом языке. Есть ли лучший способ реализовать это в F #.

Спасибо!

Answer 1

Для перестановок небольших списков, я использую следующий код:

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) 

Он работает следующим образом: функция «DISTRIB» распространяет данный элемент на всех позициях в списке, например:

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

Функция perms работает (рекурсивно) следующим образом: распределяет головку списка по всем перестановкам своего хвоста.

Функция распределения будет медленной для больших списков, поскольку она использует оператор @ много, но для списков разумной длины (< = 10) код выше работает нормально.

Предупреждение: если ваш список содержит дубликаты, результат будет содержать идентичные перестановки. Например:

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

Хорошая вещь об этом коде является то, что он возвращает последовательность перестановок, вместо того, генерируя их все сразу.

Конечно, генерация перестановок с императивным алгоритмом на основе массивов будет (намного) быстрее, но этот алгоритм в большинстве случаев послужил мне хорошо.

Answer 2

Это зависит от того, что вы подразумеваете под «лучше». Я считаю, что это будет немного более элегантно, но это может быть делом вкуса:

(* 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)) 

Это может обрабатывать списки с повторяющимися элементами, хотя это приведет к дублированию перестановок.

Answer 3

Вот решение, которое я дал в своей книге F# for Scientists (страницы 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

Вот другая последовательность-версии, мы надеемся, более удобным для чтения, чем голосовавшие ответ. Эта версия похожа на версию Джона с точки зрения логики, но использует выражения вычислений вместо списков. Первая функция вычисляет все способы вставки элемента x в список l. Вторая функция вычисляет перестановки. Вы должны иметь возможность использовать это в больших списках (например, для поиска грубой силы во всех перестановках набора входов).

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

ИМХО лучшее решение должно облегчить тот факт, что F # является функциональным языком так имхо решение должно быть как можно ближе к определению того, что мы имеем в виду, как перестановка там, насколько это возможно. Таким образом, перестановка является таким экземпляром списка вещей, где глава списка каким-то образом добавляется к перестановке остальной части входного списка. Решения Эрла показывает, что в довольно образом:

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

принятого Фроном «программирования Erlang» книги

Существует оператор списка понимания используется в решении упомянутый здесь стажер stackoverflowers есть помощник функция, которая делает подобную работу в основном я бы голосовать за решение без каких-либо видимых петель и т.д., только чистая функция определения

Answer 6

В духе внушения Cyrl, вот это последовательность постижение версия

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

где remove простая функция, которая удаляет данный элемент из списка

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