3

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

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

这是问题所在：

两个列表

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 之前，否则，所有交错都是可能的）

我希望我很清楚，并且您可以帮助我。

十分感谢。

4

2 回答 2

5

既然是作业，这里有一些提示：

1）。该函数将采用两个相同类型的列表'a list并返回一个'a list list.

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

2）。如果一个列表为空，则结果是由另一个列表组成的单例列表。
3）。假设您想interleave在两个非空列表x::xs和y::ys. 有两种交织。第一种x作为结果列表的头部，您可以将其放入x任何从interleave xs (y::ys). 第二种具有y作为新的头，您可以预先y添加到从 获取的任何列表中interleave (x::xs) ys。

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

于 2012-09-27T18:55:41.540 回答
3 
(* Each interleaving of non-empty lists lst1 = [x1; x2; ...; xm]
   and lst2 = [y1; y2; ...; yn] begins either with x1 or with y1.
   Thus we may get all the interleavings as follows:

   1. Compute all interleavings of [x2; ...; xm] and [y1; ...; yn]
      and prepend x1 to each one of them.

   2. Compute all interleavings of [x1; ...; xm] and [y2; ...; yn]
      and prepend y1 to each one of them.

   Append the lists obtained in steps 1 and 2 to get all possible
   interleavings. The border cases is when either one of the lists
   is empty, but that is easy to figure out. Here is the corresponding
   code.
*)

let rec interleave lst1 lst2 =
  match lst1, lst2 with
    | [], ys -> [ys]
    | xs, [] -> [xs]
    | x :: xs, y :: ys ->
        (List.map (fun zs -> x :: zs) (interleave xs (y::ys))) @
        (List.map (fun zs -> y :: zs) (interleave (x::xs) ys))

测试用例：

# interleave [1;2] [100;200;300] ;;
- : int list list =
[[1; 2; 100; 200; 300]; [1; 100; 2; 200; 300]; [1; 100; 200; 2; 300];
[1; 100; 200; 300; 2]; [100; 1; 2; 200; 300]; [100; 1; 200; 2; 300];
[100; 1; 200; 300; 2]; [100; 200; 1; 2; 300]; [100; 200; 1; 300; 2];
[100; 200; 300; 1; 2]]

注意：在 Ocaml 中，列表是单态的，所以我们不能像问题中所建议的那样交错字符串和整数。或者换一种说法，因为我们必须使用 sum 类型。

于 2012-09-28T00:11:06.040 回答