Найдите наименьшую подпоследовательность k различных элементов в списке - PullRequest
Новая
       15

Найдите наименьшую подпоследовательность k различных элементов в списке

0 голосов
/ 29 марта 2019

Я супер новичок в sml. Я пытаюсь написать простой код, который принимает массив из 5 позиций с определенными числами и возвращает длину наименьшего подмассива, который содержит все числа. Однако я получаю много сообщений об ошибках, которые не могу найти в Google. Может кто-нибудь мне помочь? Код следующий 

 fun Min x y = if x>y then return y else return x
    local
        val a = Array.array (3,0)
        val cordela = Array.array(5,0)
        val k=0
        val front=0
        val tail=0
        val min=5
        update(cordela,0,1)
        update(cordela,1,3)
        update(cordela,2,3)
        update(cordela,3,2)
        update(cordela,4,1)
    in   
        fun loop front = 
            case k>3 of
                if sub(a,sub(cordela,front)-1) = 0 then k=k+1 else()
                update(a,sub(cordela,front)-1),sub(a,sub(cordela,front)-1)+1)
                front = front +1
            | 
                min= Min (front-tail) min
                if sub(a,sub(cordela,front)-1) = 0 then k=k-1 else()
                update(a,sub(cordela,front)-1),sub(a,sub(cordela,front)-1)-1)
                tail=tail+1

            if 5>front then loop front+1 else min
    end

Сообщения об ошибках, которые я получаю: 

pl2.sml:16.13-16.15 Error: syntax error: replacing  OF with  LBRACKET
pl2.sml:18.36 Error: syntax error: inserting  LPAREN
pl2.sml:20.4 Error: syntax error: replacing  BAR with  EQUALOP
pl2.sml:22.5 Error: syntax error: inserting  LPAREN
pl2.sml:26.4 Error: syntax error: inserting  LPAREN
pl2.sml:27.2 Error: syntax error found at END

Редактировать: я пытаюсь написать этот код в sml. Написано на с ++ 

while(front < N){
        if( k < K ){
            if ( e[cordela[front]-1] == 0 ) k += 1;
            e[cordela[front]-1] +=1;
            front++ ;
        }
        else{
            min = MIN(front - tail ,min);
            if ( e[cordela[tail]-1] ==1 ) k -= 1;
            e[cordela[tail]-1] -= 1;
            tail++;
        }
    }

1 Ответ

2 голосов
/ 01 апреля 2019

Как говорит Джон Колман, SML / NJ не будет выдавать очень полезные сообщения об ошибках. Вместо этого вы можете попробовать установить Moscow ML , поскольку это дает лучшие сообщения об ошибках. К сожалению, с этим кодом на синтаксическом уровне есть некоторые проблемы, которые мешают компилятору выдавать значимую ошибку. Вот несколько советов по правильному синтаксису, чтобы вы могли сосредоточиться на проблемах алгоритма:

  • Не используйте local, используйте let.
  • Соответствует каждому ( с ); у вас слишком много ) с.
  • Объявите fun loop ... = ... внутри let и in.

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

    fun smallest_subarray (needles : Array.array, haystack : Array.array) =
    let
      val ... = ...
      fun loop ... = ...
    in
      if Array.length needles > Array.length haystack
      then ...
      else loop ...
    end

Что, если нет решения проблемы, что вернет функция? ~1? NONE

Если вы пытаетесь преобразовать программу на C ++ в SML, попробуйте включить функциональную часть таким образом, чтобы было очевидно, какие идентификаторы являются аргументами функции, и попытайтесь назвать их логически; Я понятия не имею, что такое cordela, e и k, или если N является функцией размера входного массива или константой.

Поскольку идиоматическое решение в SML использует рекурсию (вызывающую функцию), а не итерацию (while), вы имеете дело как с нетривиальной проблемой алгоритма , так и с другой парадигмой. Вместо этого попробуйте решить аналогичную, но более простую проблему, где алгоритм более тривиален, и примените парадигму рекурсии.

Например, попробуйте написать функцию, которая находит позицию элемента в отсортированном массиве с помощью бинарного поиска: 

fun find x arr =
    let
      fun loop ... = ...
    in
      loop ...
    end

Функция loop принимает границы поиска (например, i и j) в качестве аргумента и возвращает либо SOME i, если x найден в позиции i, либо NONE. Вы могли бы расширить эту проблему в направлении исходной проблемы, пытаясь написать функцию, которая определяет, встречается ли входной массив needles в другом входном массиве haystack в порядке, указанном в needles. Сначала вы можете предположить, что needles и haystack отсортированы, а затем предположить, что это не так.

...