3

私はここでかなりの挑戦の前にいます、そしてあなたが少しの助けを提供できることを願っています。

私はたくさん試し、検索しましたが、成功しませんでした。

ここに問題があります：

2つのリスト

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

各リスト内の順序を尊重して、2つのリストで可能なすべてのインターリーブのリストを返す関数は何ですか。

例えば ​​：

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）。この関数は、同じタイプの2つのリストを受け取り'a list、を返します'a list list。

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

2）。一方のリストが空の場合、結果はもう一方のリストで構成されるシングルトンリストになります。
3）。interleave空でない2つのリストx::xsとを実行したいとしますy::ys。インターリーブには2種類あります。最初の種類はx、結果のリストの先頭として、xから戻るリストの先頭に配置しますinterleave xs (y::ys)。2番目の種類は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では、リストは単形であるため、質問で示唆されているように、文字列と整数をインターリーブすることはできません。または、別の言い方をすれば、合計タイプを使用する必要があります。

于 2012-09-28T00:11:06.040 に答える