Блог

Если у меня есть такой список, как этот:

 [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 содержит все элементы слева от первого элемента. и перечислите два всех элемента справа.
• затем проверьте, соответствует ли элемент какому-либо из двух списков.
• если это действительно так, установите текущее значение max для элемента.
• теперь соедините следующий элемент справа от текущего элемента в исходном списке с текущим элементом и снова посмотрите в list_one и list_two, если есть совпадение.
• после того, как длина объединения достигнет точки, в которой оно gt;(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, но я думаю, что может быть более простой способ сделать это.

Я не уверен, что понимаю проблему, основываясь на ваших примерах. Если вы пытаетесь найти последовательности повторяющихся значений, это довольно просто. Давайте рассмотрим способ ее решения с точки зрения List.fold_left .

 List.fold_left   (fun (max_seq, cur_seq) x -gt;  match (max_seq, cur_seq) with  (* Set the info up on the first iteration. *)  | None, None -gt; (Some (1, x), Some (1, x))  (* These should basically never occur. *)  | None, Some (cur_len, cur_val) -gt; (cur_seq, cur_seq)  | Some (max_len, max_val), None -gt; (max_seq, max_seq)  (* Where the real magic happens. *)  | Some (max_len, max_val), Some (cur_len, cur_val) -gt;   if x = cur_val amp;amp; cur_len gt;= 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) -gt; (cur_seq, cur_seq)  | Some (max_len, max_val), None -gt; (max_seq, max_seq)  

Здесь происходит настоящее волшебство:

 | Some (max_len, max_val), Some (cur_len, cur_val) -gt;   if x = cur_val amp;amp; cur_len gt;= 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))  

Когда мы складываем каждое значение в списке:

1. Если это продолжение текущей последовательности, а длина либо такая же, либо больше максимальной последовательности, то у нас есть новая максимальная последовательность.
2. В противном случае у нас есть продолжение последовательности, но это не новый макс.
3. В противном случае нам придется отслеживать новую последовательность.

Конечный результат даст два значения, представляющих максимальную длину и значение последовательности, а также текущую последовательность и значение. Мы можем использовать сопоставление шаблонов, чтобы извлечь эту информацию и удалить то, что нам нужно.

Например:

 let max_seq lst =  let (max, _) = List.fold_left   (fun (max_seq, cur_seq) x -gt;  match (max_seq, cur_seq) with  | None, None -gt; (Some (1, x), Some (1, x))  | None, Some (cur_len, cur_val) -gt; (cur_seq, cur_seq)  | Some (max_len, max_val), None -gt; (max_seq, max_seq)  | Some (max_len, max_val), Some (cur_len, cur_val) -gt;   if x = cur_val amp;amp; cur_len gt;= 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  | [] -gt; init  | x::xs -gt; foldl f (f init x) xs