Мне нужно выполнить проектирование списка списков, который возвращает все комбинации с каждым элементом из каждого списка. Например:
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]].
Я придумал функцию:
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)
и тест:
#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;;
Теперь функция довольно медленная, а N = 10
требуется больше 10 секунд. Более того, я считаю, что решение неестественно, потому что мне приходится разбивать один и тот же список двумя разными способами. Любое предложение, как я могу улучшить производительность и читаемость функции?