如果我有這樣的串列：
[i;i;i;a;b;b;a;i;i;c]
(*the longest repeating sequence would be [i;i]*)
[i;i;i;i]
(*here the max_pattern would be [i;i] (has to repeat, no overlapping*)
[t;f;f;t]
(*here it would be [t] as t is, in this case,
the first element that has a repeating pattern in the list*)
我的點子：
從串列中取出第一個元素并劃分串列 - 其中 list_one 包含第一個元素左側的所有元素。和 list_two 右邊的所有元素。
然后檢查該元素是否在兩個串列之一中匹配。
如果它確實將當前最大值設定為元素。
現在將原始串列中當前元素右側的下一個元素連接到當前元素，如果有匹配，則再次查看 list_one 和 list_two 。
在連接的長度到達
>(size_of list / 2)停止點之后。現在轉到第一步但使用下一個元素并重復直到檢查串列中的每個元素。
例子：
[t;f;f;t]
(*first round*)
[t][][f;f;t]
(*match in last elem*)
current_max = [t]
(*second round*)
[t;f][][f;t]
(*from here on no more matches*)
(*go to the next element, split lists again, and proceed with mentioned steps*)
[f][t][f;t]
(*match in f*)
(*repeat from here on...*)
不知道這個演算法有沒有缺陷。我正在嘗試在 OCaml 中實作這一點，但我認為可能有一種更簡單的方法來做到這一點。
uj5u.com熱心網友回復：
根據您的示例，我不確定我是否理解問題。如果您要查找重復值的序列，這非常簡單。讓我們來看看解決它的方法List.fold_left。
List.fold_left
(fun (max_seq, cur_seq) x ->
match (max_seq, cur_seq) with
(* Set the info up on the first iteration. *)
| None, None -> (Some (1, x), Some (1, x))
(* These should basically never occur. *)
| None, Some (cur_len, cur_val) -> (cur_seq, cur_seq)
| Some (max_len, max_val), None -> (max_seq, max_seq)
(* Where the real magic happens. *)
| Some (max_len, max_val), Some (cur_len, cur_val) ->
if x = cur_val && cur_len >= max_len then
let new_val = Some (cur_len 1, cur_val) in
(new_val, new_val)
else if x = cur_val then
(max_seq, Some (cur_len 1, cur_val))
else
(max_seq, Some (1, x))
)
(None, None)
[1; 1; 5; 7; 2; 2; 2; 2; 2; 2; 8; 8; 1; 1; 1; 1; 1]
結果：
(Some (6, 2), Some (5, 1))
因為我們需要處理空串列的前景，我們將使用option代表觀察到的最大序列的元組的型別，以及我們正在跟蹤的當前序列。
鑒于當我們觀察到兩個值都是 時None，我們將最大序列和當前序列都設定為迄今為止觀察到的唯一值，序列長度為1，接下來的兩種情況基本上就是為了確保徹底匹配：
| None, Some (cur_len, cur_val) -> (cur_seq, cur_seq)
| Some (max_len, max_val), None -> (max_seq, max_seq)
真正的魔法發生在這里：
| Some (max_len, max_val), Some (cur_len, cur_val) ->
if x = cur_val && cur_len >= max_len then
let new_val = Some (cur_len 1, cur_val) in
(new_val, new_val)
else if x = cur_val then
(max_seq, Some (cur_len 1, cur_val))
else
(max_seq, Some (1, x))
當我們折疊串列中的每個值時：
如果它是當前序列的延續，并且長度等于或大于最大序列，那么我們有一個新的最大序列。
否則，我們有一個序列的延續，但它不是一個新的最大值。
否則，我們有一個新的序列要跟蹤。
最終結果將使用兩個值表示最大序列長度和值，以及當前序列和值。我們可以使用模式匹配來提取這些資訊并剔除我們需要的資訊。
例如：
let max_seq lst =
let (max, _) = List.fold_left
(fun (max_seq, cur_seq) x ->
match (max_seq, cur_seq) with
| None, None -> (Some (1, x), Some (1, x))
| None, Some (cur_len, cur_val) -> (cur_seq, cur_seq)
| Some (max_len, max_val), None -> (max_seq, max_seq)
| Some (max_len, max_val), Some (cur_len, cur_val) ->
if x = cur_val && cur_len >= max_len then
let new_val = Some (cur_len 1, cur_val) in
(new_val, new_val)
else if x = cur_val then
(max_seq, Some (cur_len 1, cur_val))
else
(max_seq, Some (1, x))
)
(None, None)
lst
in
max
現在我們可以簡單地在串列中呼叫它。
utop # max_seq [1; 1; 5; 7; 2; 2; 2; 2; 2; 2; 8; 8; 1; 1; 1; 1; 1];;
- : (int * int) option = Some (6, 2)
作為該語言的新手，如果它可以幫助您理解List.fold_left，那么它是一個非常容易實作的功能，并且在嘗試將您的大腦圍繞它時查看該實作通常很有用。我會打電話給我的版本foldl。
let rec foldl f init lst =
match lst with
| [] -> init
| x::xs -> foldl f (f init x) xs
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/368800.html
上一篇：串列串列中的字串