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

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

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 #.

Спасибо!

Ответ 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]]

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

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

Ответ 2

Вот решение, которое я дал в моей книге 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)

Ответ 3

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

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

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

Ответ 4

Здесь другая версия на основе последовательности, надеюсь, более читаема, чем проголосовавший ответ. Эта версия похожа на версию Jon с точки зрения логики, но использует выражения вычислений вместо списков. Первая функция вычисляет все способы вставки элемента 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
      }

Ответ 5

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

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

Ответ 6

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

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

взятых из книги программирования erlang

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