# Interleave two lists, preserving the order of elements in their original list

I need to write an OCaml program that return all possible zip of two lists together while preserving the order of the element in each list. For example, if we zip the lists [1;2] and [3;4], we get [[1;2;3;4];[1;3;4;2];[3;1;2;4];[1;3;2;4];[3;1;4;2];[3;4;1;2]].

My naïve approach is to append each element in the first list one by one into the second list while making sure that the order of elements in the first list is preserved when inserted into the second list. Please show me the simple recursive structure.

Here are my codes :

let rec insert item list =
match list with
|[]-> [[item]]
|x::xs-> (item::list)::(List.map (fun y-> x::y) (insert item xs))

let breakIntoTwo  list item=
let rec helper acc ll itemm=
match ll with
|[]->(acc,[])
|x::xs -> if x= itemm then (acc,ll)
else helper (acc@[x]) xs itemm
in helper [] list item

let rec insertl item list nextItem=
match breakIntoTwo list nextItem with
|(a,b) -> List.map (fun y -> y@b) (insert item a)

let rec insertll item listoflists nextItem=
match listoflists with
|[]-> []
|x::xs-> (insertl item x nextItem) @ (insertll item xs nextItem)

let rec zip list1 list2=
match list1 with
|[]-> [list2]
|[a]-> insert a list2
|x::xs::xss -> insertll x (zip (xs::xss) list2) xs