recursion - 通过递归函数 (Ocaml) 交错两个列表

Question

我在这里面临着相当大的挑战，希望您能提供一点帮助。

我已经尝试并搜索了很多，但没有成功。

问题来了:

两个列表

List1 : [a1; a2; ...; an]
List2 : [b1; b2; ...; bn]

返回两个列表的所有可能的交错列表的函数是什么，尊重每个列表中的顺序。

例如:

myFunction [1; 2] ['a'; 'b'; 'c'] = [ 
    [1; 2; 'a'; 'b'; 'c']; 
    [1; 'a'; 2; 'b'; 'c']; 
    [1; 'a'; 'b'; 2; 'c']; 
    [1; 'a'; 'b'; 'c'; 2]; 
    ['a'; 1; 2; 'b'; 'c']; 
    ['a'; 1; 'b'; 2; 'c']; 
    ['a'; 1; 'b'; 'c'; 2]; 
    ['a'; 'b'; 1; 2; 'c']; 
    ['a'; 'b'; 1; 'c'; 2]; 
    ['a'; 'b'; 'c'; 1; 2] 
]

对于那些已经注意到的人来说，它基本上是在考虑 2 个并发程序，以及 2 个程序启动时所有可能的执行(1 总是在 2 之前，a 总是在 b 之前和 c 之前，否则，所有交错都是可能)

我希望我说的很清楚，希望你能帮助我。

非常感谢。

Answer 1

由于是作业，这里有一些提示:

1)。该函数将获取两个相同类型的列表 'a list 并返回一个 'a list list。

val interleave: 'a list -> 'a list -> 'a list list

2)。如果一个列表为空，则结果是由另一个列表组成的单例列表。
3)。假设您想在两个非空列表 x::xs 和 y::ys 上执行 interleave。有两种交织。第一种以 x 作为结果列表的头部，您可以将 x 放在从 interleave xs (y::ys)< 返回的任何列表的开头。第二种以 y 作为新头，您可以将 y 添加到从 interleave (x::xs) ys 获得的任何列表中。

有了这些提示，我认为您可以创建一个带有一些模式匹配案例的递归函数来解决问题。