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

Вот решение, которое я дал в своей книге F # для ученых (стр. 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 2

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

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 10 [1;2;3] --> [[10;1;2;3];[1;10;2;3];[1;2;10;3];[1;2;3;10]]

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

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

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

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

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

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

Answer 3

В духе предложения Сайрла, вот версия для понимания последовательности

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

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

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

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

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

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

взято из книги "Erlang для программирования"

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