I have to do projection of a list of lists which returns all combinations with each element from each list. For example:
projection([[1]; [2; 3]]) = [[1; 2]; [1; 3]].
projection([[1]; [2; 3]; [4; 5]]) = [[1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]].
I come up with a function:
let projection lss0 =
let rec projectionUtil lss accs =
match lss with
| [] -> accs
| ls::lss' -> projectionUtil lss' (List.fold (fun accs' l ->
accs' @ List.map (fun acc -> acc @ [l]) accs)
[] ls)
match lss0 with
| [] -> []
| ls::lss' ->
projectionUtil lss' (List.map (fun l -> [l]) ls)
and a testcase:
#time "on";;
let N = 10
let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i));;
let fss1 = projection fss0;;
The function is quite slow now, with N = 10
it takes more than 10 seconds to complete. Moreover, I think the solution is unnatural because I have to breakdown the same list in two different ways. Any suggestion how I can improve performance and readability of the function?