Заменить часть списка в Prolog

      Комментарии к записи Заменить часть списка в Prolog отключены

В этой теме 5 ответов, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 12 мес. назад.

  • Автор
    Сообщения
  • #1783

    questioner
    Участник

    Дан список из букв a,b,c. Нужно заменить все ab на ba за одну рекурсию. Замену выполнять до тех пор, пока она возможна. На SWI Prolog.

    Не могу вычленить два нужных символа подряд. Нужно ведь распознать a,b. и заменить на b,a. Как это организовать от начала до конца я не знаю.
    Пример:

    X=[a,b,b,a,b], swap_ab(X, Swapped).
    Swapped = [b,b,b,a,a]

  • #1784

    swap_ab([97, 98|T], [98, 97|TR]):-
        !, swap_ab(T, TR).
    swap_ab([H|T], [H|TR]):-
        !, swap_ab(T, TR).
    swap_ab(_, []):-!

    97 – это символ ‘a’, 98 – ‘b’. Вместо кодов символов можно можно использовать char_code.
    Функция отделяет два первых символа если она составляют “ab”, обрабатывает остальные символы рекурсивно. К полученному результату дописывает “ba”.
    Если отделить символы “ab” от начала списка не получилось, то отделяется лишь один элемент, который дописывается к результату рекурсивной обработки остальных.
    В противном случае (если не получилось отделить первый элемент, т.е. если список пуст) – функция возвращает пустой список в качестве результата.

    • #1785

      questioner
      Участник

      Замену нужно выполнять до тех пор, пока исходная строка отличается от полученного результата. У меня не получается сделать всё это одной рекурсией.

      • #1786

        «Одной рекурсией» — это так, что-ли?

        swap_ab(Buffer, [], Buffer):-!.
        swap_ab(Buffer, [97, 98|Tail], Swapped):-
          !, append(Buffer, [98, 97|Tail], SwappedList),
          swap_ab([], SwappedList, Swapped).
        swap_ab(Buffer, [Head|Tail], Swapped):-
          append(Buffer, [Head], BufferWithHead),
          !, swap_ab(BufferWithHead, Tail, Swapped).

        Тут используется метод накапливающего параметра – результат накапливается в первом аргументе функции до тех пор, пока входной список не окажется пустым. При пустом входном списке решением является накопленный в буфере результат. Изначально буфер пуст. Символы из основного списка постепенно попадают в буфер, т.е. конкатенация буфера и необработанной части списка на каждом шаге представляет собой промежуточный результат.
        Функция пытается отделить от списка искомую комбинацию символов и, если это удается сделать:

        • при помощи стандартного предиката append из буфера и необработанной части формирует новый исходный список, в котором комбинация заменена;
        • выполняет рекурсивную обработку списка, при этом в качестве буфера передается пустой список, т.к. буфер уже включен в новый обрабатываемый список;

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

        • #1787

          questioner
          Участник

          Не могли бы вы преобразовать коды обратно в символы. Я видел только те предикаты, которые делают обратную задачу, теперь все таки нужно, чтобы выдавалось буквами, а не кодами, помогите, пожалуйста!

          • #1788

            Стандартный предикат string_to_list выполняет как преобразование строки в список кодов, так и обратную работу.

            swap_ab([], "aaabbb", SwappedList), string_to_list(SwappedString, SwappedList).
            SwappedList = [98, 98, 98, 97, 97, 97],
            SwappedString = "bbbaaa".

Для ответа в этой теме необходимо авторизоваться.