Todos os picaretas de uma lista no F # - mais elegante e simples

Question

Alguém poderia propor melhor e / ou implementação mais elegante deste:

let each xs = 
    let rec each' acc left right = 
        match right with
        | [] -> acc
        | right ->  let new_left  = left @ [List.hd right]
                    let next   = List.tl right
                    let result = (List.hd right), left @ next
                    each' (result::acc) new_left next
    each' [] [] xs

É fazer isso:

> each [1..3];;
val it : (int * int list) list = [(3, [1; 2]); (2, [1; 3]); (1, [2; 3])]

Esta função pode retornar o resultado em sentido inverso também. A idéia é fazer com que todos os elementos como tuplas com um elemento e uma lista de elementos de descanso.

Answer 1

A semântica é um pouco diferente aqui, mas a partir do exemplo que você dá Set pode ser uma boa opção:

let each xs =
    let X = set xs                           
    [ for x in xs -> (x, X - set [x]) ]


> fsi.AddPrinter( fun (x:Set<int>) -> sprintf "%A" (Set.to_list x))
> each [1..3];;
> val it : (int * Set<int>) list = [(1, [2; 3]); (2, [1; 3]); (3, [1; 2])]

// Edited as per comments.

Answer 2

Como sobre: ??

let rec each = function
| x :: xs -> (x,xs) :: (each xs |> List.map (fun (y,ys) -> (y,x::ys)))
| [] -> []

Ou uma cauda equivalente recursiva (produzindo as listas em ordem inversa):

let each lst =
  let rec helper acc seen = function
  | [] -> acc
  | x :: xs -> 
      helper ((x,seen)::(acc |> List.map (fun (y,ys) -> (y,x::ys)))) (x::seen) xs
  helper [] [] lst

Answer 3

let each l = l |> List.map (fun x -> x, List.filter (fun y -> y <> x) l)

Nota: esta função é O (n ^ 2). Considere o uso de Seq.map e Seq.filter vez:

let each l = l |> Seq.map (fun x -> x, Seq.filter (fun y -> y <> x) l)

versão Seq tem um desempenho de O (n).

Answer 4

Isto não é muito melhor, se houver, que a solução original, mas aqui vai. Esta versão evita a lista Anexa usando uma função de utilidade para mesclar a lista esquerda revertida com a cauda da direita. Além disso, ele usa correspondência de padrão em vez das funções de cabeça e cauda.

let rec ljoin revleft right =  
  match revleft with 
       | [] -> right 
       | (x::xs) -> ljoin xs (x::right)                                                                                   
let each xs =
    let rec each' acc left right =
       match right with
       | [] -> acc
       | (y::ys) ->
           let result = y, ljoin left ys 
           each' (result::acc) (y::left) ys
    each' [] [] xs

Answer 5

Outra proposição de meus que usam Fold. É função linear S (N). Mas definitivamente não é tão elegante e simples como a solução da DannyAsher:

let each5 xs =  let fu (left, next, acc) x = left@[x], List.tl next, (x, left@(List.tl next))::acc
                let (x, y, res) = List.fold fu ([], xs, []) xs
                res