All picks of a list in F# - more elegant and simple

Question

Could someone propose better and/or more elegant implementation of this:

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

It do that:

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

This function could return the result in reverse direction, too. The idea is to get all elements as tuples with an element and list of rest elements.

Answer 1

The semantic is slightly different here, but from the example you give Set might be a good fit:

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.

• The_Ghost: Very elegant solution! But what is the algorithmic complexity of it by your oppinion?
• Daniel Asher: I believe this should be O(n log n).
• kvb: @DannyAsher - I'm pretty sure that it's O(n^2) at best, since you're computing set xs each time through the loop. Hoisting that calculation out will make the function dramatically faster.
• Daniel Asher: hi kvb - sorry, I was assuming that set xs would be taken out of the loop. The first edit actually has that, but I elided it. Sometimes concision gets the better of me <blush>.
• The_Ghost: I think both edits are the same. And the compiler "sees" that xs is same set and will not recalculate it each time (remember the laziness). So I think it'll take anyway O(n log n). May be only a profiler or debugger could prove who's right...

Answer 2

How about:

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

Or a tail recursive equivalent (producing the lists in reverse order):

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

• gradbot: Sorry, i re-ran this with a more sane value of 4000 and it runs fine, +1.
• gradbot: By the way "as" is a reserved word in the VS 2010 Beta.
• kvb: @gradbot - Thanks, I've changed a,as,b,bs -> x,xs,y,ys to avoid the keyword issue. That's the danger of posting without a compiler handy...
• The_Ghost: Your second function is more than two times faster than the first one.

Answer 3

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

Note: this function is O(n^2). Consider using Seq.map and Seq.filter instead:

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

Seq version has a performance of O(n).

• gradbot: I guess depending on how you define Big O Seq is O(n) however if you iterate over it then it will be O(N^2) since the function returns a set n with elements of size n.
• ShuggyCoUk: thank you I was not aware of the behaviour of @ - since your sequence one is rather superior I've just deleted mine
• ShuggyCoUk: incidentally your functions do have one flaw: try each (1::2::2::3::[])
• The_Ghost: let each l = l |> Seq.map (fun x -> x, Seq.filter ((<>) x) l)
• The_Ghost: Second function gives 1400 times faster time than the first one.

Answer 4

This is not much better, if any, than the original solution, but here it goes. This version avoids the list appends by using a utility function to merge the reversed left list with the tail of the right. Also, it uses pattern matching instead of the head and tail functions.

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

Other proposition of mine using Fold. It is linear function O(N). But definitely not so elegant and simple as DannyAsher's solution:

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

• The_Ghost: Faster than kvb about minimum 3x for 5000 elements.