2

有人可以提出更好和/或更优雅的实现：

让每个 xs =
    让 rec each' acc 左右 =
        与
        | [] -> ACC
        | 右 -> 让 new_left = 左 @ [List.hd 右]
                    让下一个 = List.tl 对
                    let result = (List.hd right), left @ next
                    each' (result::acc) new_left next
    每个' [] [] xs

它这样做：

> 每个 [1..3];;
验证它: (int * int list) list = [(3, [1; 2]); (2, [1; 3]); (1, [2; 3])]

该函数也可以反向返回结果。这个想法是将所有元素作为具有元素和剩余元素列表的元组。

4

5 回答 5

7

这里的语义略有不同，但从你给出的例子来看Set可能很合适：

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.
于 2009-07-27T18:41:09.490 回答
2

怎么样：

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

或尾递归等价物（以相反的顺序生成列表）：

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
于 2009-07-27T18:43:01.423 回答
1 
let each l = l |> List.map (fun x -> x, List.filter (fun y -> y <> x) l)

注意：这个函数是 O(n^2)。考虑使用 Seq.map 和 Seq.filter 代替：

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

Seq 版本的性能为 O(n)。

于 2009-07-27T18:06:48.093 回答
0

这并不比原来的解决方案好多少（如果有的话），但它就是这样。此版本通过使用实用函数将反转的左侧列表与右侧的尾部合并来避免列表追加。此外，它使用模式匹配而不是 head 和 tail 函数。

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
于 2009-07-27T18:35:13.967 回答
0

我使用折叠的其他提议。它是线性函数 O(N)。但绝对不像 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
于 2009-07-28T10:29:53.497 回答