1

サブリストをリストの別のサブリスト に置き換えて、次の結果を達成したいと考えています。lista listblisto

let replace_sublist listo lista listb =

listo で、sublist = lista がある場合、この sublist を listb に置き換えます。

Pythonで実装された同様の質問を見つけました。

リンク: Python でサブリストを別のサブリストに置き換える

なにか提案を？ありがとう。

4

3 に答える 3

2 
type 'a strip_result =
| No_match
| Too_short
| Tail of 'a list

(** [try_strip li subli] tries to
    remove the prefix [subli] from the list [li] *)
let rec try_strip li subli = match li, subli with
  | _, [] -> Tail li
  | [], _ -> Too_short
  | hli::tli, hsub::tsub ->
    if hli <> hsub then No_match
    else try_strip tli tsub

let rec replace_sublist li from_sub to_sub =
  match li with
    | [] -> []
    | head::tail ->
      match try_strip li from_sub with
        | Too_short -> li
        | No_match -> head :: replace_sublist tail from_sub to_sub
        | Tail rest -> to_sub @ replace_sublist rest from_sub to_sub

let test =
  (* simple replace *)
  assert (replace_sublist [1;2;3;4] [2;3] [-2;-3] = [1;-2;-3;4]);
  (* multiple replace *)
  assert (replace_sublist [1;2;3;2;4] [2] [0] = [1;0;3;0;4]);
  (* stop while partial match *)
  assert (replace_sublist [1;2;3;4] [3;4;5] [0] = [1;2;3;4]);
  (* stop at match *)
  assert (replace_sublist [1;2;3;4] [3;4] [2;1] = [1;2;2;1]);
  (* tricky repeating sublist case *)
  assert (replace_sublist [2;2;3] [2;3] [0] = [2;0]);
  ()


(* tail-rec version: instead of concatenating elements before
   the recursive call
     head :: replace_sublist ...
     to_sub @ replace_sublist ...
   keep an accumulator parameter `acc` to store the partial result,
   in reverse order
     replace (t :: acc) ...
     replace (List.rev_append to_sub acc) ...
*)
let replace_sublist li from_sub to_sub =
  let rec replace acc li = match li with
    | [] -> List.rev acc
    | head::tail as li ->
      match try_strip li from_sub with
        | Too_short -> List.rev (List.rev_append li acc)
        | No_match -> replace (head :: acc) tail
        | Tail rest -> replace (List.rev_append to_sub acc) rest
  in replace [] li

try_stripPS: このアルゴリズムは、失敗した後、リスト内の次の要素だけでなく、新しい一致を開始できないことがわかっているいくつかの要素に移動することで改善できることはよく知られています。ただし、このジャンプする要素の数は のような単純なものではなくList.length from_sub - 1、パターン構造から事前に計算する必要があります (「トリッキーな繰り返しサブリスト」の存在に依存します)。これがクヌース・モリス・プラットのアルゴリズムです。

于 2013-03-15T14:52:26.613 に答える
1

これは基本的に部分文字列の検索と置換です。リストが長い場合は、Knuth-Morris-Pratt のような高度なアルゴリズムを使用して、2 次数の比較を回避することをお勧めします。

(私はいくつかのコードを書くつもりでしたが、Bug Gasche はすでに素晴らしい仕事をしていました。)

于 2013-03-15T14:57:39.943 に答える
1

あなたはそのようなことをすることができます:

let replace listo lista listb =
  let rec loop listo lista listb accu =
    match listo with
      [] -> List.rev accu
    | x :: xs ->
      if xs = lista then List.rev_append (x :: accu) listb
      else loop xs lista listb (x :: accu) in
  loop listo lista listb []

まず、 sublist を見つける必要がありますlista。このリストを見つけたら、アキュムレータaccuを元に戻してから、listb

于 2013-03-15T09:57:35.423 に答える