Поиск режима списка int в SML и где он встречается без библиотечных функций

Я пытаюсь найти режим или значение, которое встречается чаще всего. Я хочу такую ​​​​функцию, как:

mode:' 'a list -> (''a * int) list

и он возвращает режим и место его возникновения, если нет ничьей, а затем возвращает все вхождения, например:

mode([1,1,2,3,5,8]) ===> [(1,2)]
mode([1,3,5,2,3,5]) ===> [(3,2),(5,2)]
mode([true,false,true,true]) ====>[(true,3)]

Я пытаюсь сделать это без библиотечных функций в SML.

пока что я получил:

fun mode(L)=
if null L then nil
else if hd L= hd (tl L) then 1+mode(hd(tl L))
else mode(tl L);

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

Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
0
0
184
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы пытаетесь решить упражнение, состоящее из многих частей, с несколькими более простыми упражнениями перед ним. Судя по вашему нынешнему прогрессу, не думали ли вы о решении каких-то очень похожих упражнений, ведущих к конечной цели? Обычно это хороший совет при решении задач программирования: сведите текущую задачу к более простым задачам и решите их.

Я бы попробовал сначала решить эту проблему

  • Создайте histogram : ''a list -> (''a * int) list над элементами списка:

    fun histogram [] = ...
      | histogram (x::xs) = ...
    

    Сделайте это, вставив каждый x с его count в гистограмму.

    fun insert (x, []) = ...
      | insert (x, (y, count) :: hist) = ...
    

    И напишите несколько тестов, которые вы можете выполнять время от времени.

  • Найдите mode : ''a list -> ''a списка:

    fun mode xs = ... (histogram xs)
    

    Сделайте это, найдя элемент на гистограмме с наибольшим количеством:

    fun findMax [] = ... (* what if the list/histogram is empty? *)
      | findMax [(x, count)] = ...
      | findMax ((x, count) :: (y, count) :: hist) = ...
    

и в конце концов попытаться решить эту проблему

  • Когда вы хорошо разбираетесь в рекурсивном представлении и навигации по обычным гистограммам, вы можете создать аннотированный histogram : (''a * int * int list) list, который не только содержит частоту каждого элемента, но и их позиции во входном списке:

    fun histogram_helper ([], _) = ...
      | histogram_helper (x::xs, i) = ... histogram_helper (xs, i+1) ...
    

    Сделайте это, вставив каждый x с его count и позицией i вместе с ранее найденными позициями is в гистограмму:

    fun insert (x, i, []) = ...
      | insert (x, i, (y, count, is) :: hist) = ...
    
  • Найдите (возможно, несколько) mode : ''a list -> (''a * int list) list списка:

    fun mode xs = ... (histogram xs)
    

    Сделайте это, найдя (возможно, несколько) элементов на гистограмме с наибольшим количеством:

    fun findMax ([],                     countMax, tmpModes) = ...
      | findMax ((x, count, is) :: hist, countMax, tmpModes) = ...
    

    где countMax : int - это частота, повторяющаяся в tmpModes : (''a * int * int list) list. Здесь countMax и tmpModes — это накопление параметров результата. Сделайте это, определив, следует ли отбросить (x, count, is) в пользу всех tmpModes, или добавить к tmpModes, или выбрать в пользу всех tmpNodes

    I am curious on how you both keep the indices of where the mode occurs and what the mode is and return them as tuples in a list.

    Да это не банально. Используя предложенное мной разделение на подзадачи, ответ на этот вопрос зависит от того, находимся ли мы в функции histogram или в функции findMax:

    В histogram вы можете хранить индексы как часть кортежа, содержащего элемент и частоту. В findMax, поскольку вы потенциально собираете несколько результатов, вам нужно отслеживать как самую высокую частоту (countMax), так и выбранные режимы временный (tmpModes); подлежит замене или добавлению в более позднем рекурсивном вызове.

    Итак, чтобы ответить на ваш вопрос: в накопительном параметре.


и небольшая обратная связь к вашему фрагменту кода

fun mode(L)=
if null L then nil
else if hd L= hd (tl L) then 1+mode(hd(tl L))
else mode(tl L);

Используйте сопоставление с образцом вместо null, hd и tl:

fun count_4s [] = 0
  | count_4s (x::xs) = (if x = 4 then 1 else 0) + count_4s xs

fun count_ns ([],    _) = 0
  | count_ns (x::xs, n) = (if x = n then 1 else 0) + count_ns (xs, n)

fun count_12 ([], ones, twos) = (ones, twos)
  | count_12 (x::xs, ones, twos) =
      if x = 1 then count_12 (xs, ones+1, twos) else
      if x = 2 then count_12 (xs, ones, twos+1) else
      count_12 (xs, ones, twos)

fun count_abc ([], result) = result
  | count_abc (x::xs, ((a, ca), (b, cb), (c, cc))) =
      count_abc (xs, if x = a then ((a, ca+1), (b, cb), (c, cc)) else
                     if x = b then ((a, ca), (b, cb+1), (c, cc)) else
                     if x = c then ((a, ca), (b, cb), (c, cc+1)) else
                     ((a, ca), (b, cb), (c, cc)))

Построение гистограммы является своего рода расширением этого, где вместо фиксированного значения, такого как 4, или фиксированного их количества, такого как ones и twos, у вас есть целый их список, и вы должны динамически искать тот, который у вас есть. got, x, и определите, нужно ли добавить его к гистограмме или увеличить на гистограмме.

Лучше всего было бы сделать это во вспомогательной функции, например, если count_abc было создано во вспомогательной функции,

fun insert_abc (x, ((a, ca), (b, cb), (c, cc))) =
    if x = a then ((a, ca+1), (b, cb), (c, cc)) else
    if x = b then ((a, ca), (b, cb+1), (c, cc)) else
    if x = c then ((a, ca), (b, cb), (c, cc+1)) else
    ((a, ca), (b, cb), (c, cc)))

fun count_abc ([], result) = result
  | count_abc (x::xs, result) =
      count_abc (xs, insert (x, result))

только вместо представления гистограммы

(''a * int) * (''a * int) * (''a * int)

ты хочешь

(''a * int) list

и insert должен быть рекурсивным, а не повторяющимся insert_abc.

Другие вопросы по теме