Блог

Главная - Вопросы по программированию - Проверка Prolog, если в 2 списках одинаковое количество элементов

Проверка Prolog, если в 2 списках одинаковое количество элементов

#prolog

#пролог

Вопрос:

Я пытаюсь понять, как сделать эту маленькую вещь. Например, у меня есть 2 списка, [1,1,2,3,4] и [2,1,4,3,1] мне нужно подтвердить, включены ли все элементы из списка 1 в список 2, поэтому, если я приведу приведенные выше списки в качестве входных данных, это должно быть правдой, но если это так [1,1,2,3,4] и [2,1,4,3,1,1] (три 1), это должно дать false , это должно быть сделано безиспользование функции сортировки.

Комментарии:

1. Необходимо рассмотреть два случая. Первый случай: списки [] и [] имеют одинаковую длину. Второй случай: списки [_ | Xs] и [_ | Ys] имеют одинаковую длину, если Xs и Ys имеют одинаковую длину length .

Ответ №1:

Я предполагаю, что вы знаете, как написать список как head и tail ( [H|L] ) .
Таким образом, вы могли бы использовать предикат member/2 , чтобы запросить, чтобы каждый элемент из первого списка также был во втором списке, но это не решило бы проблему дубликатов. Использование предиката length/2 в этом случае не поможет. Итак, вам нужно что-то, что удаляет один соответствующий элемент из списка. Вы можете либо написать свой собственный предикат поиска и удаления, либо использовать для этого предикат append/3 . append/3 считается, что 2 списка добавляются для формирования третьего, но его также можно использовать для разделения одного списка на два. Если вы укажете, что ваш элемент является головным элементом второго разделенного списка, вы в основном получаете функцию «удалить элемент». Как только вы получите 2 разделенных списка, объедините их в новый список и снова вызовите предикат, но на этот раз без элемента head из первого списка и с повторно добавленным списком. Итак, на каждом шаге вы удаляете по одному элементу из каждого списка, пока, наконец, не нажмете два пустых списка ( permut([],[]). ). Если должно появиться что-то, отличное от этих двух случаев, то два списка не являются перестановками друг друга, и предикат завершается ошибкой.

Поскольку нет смысла возвращать другие позиции, я вставил cut ( ! ) после успешного нахождения элемента во втором списке. Предикат также работает без вырезания.

 permut([],[]).
permut([H|T], Compare):-
    append(C1, [H|C2], Compare),
    !,
    append(C1, C2, Cnext),
    permut(T, Cnext).

выдает результат

 ?- permut([1,2,3,4,5],[5,4,3,2,1]).
true.

?- permut([1,2,3,4,5],[5,4,3,2,1,1]).
false.

?- permut([1,2,3,4,5,6],[5,4,3,2,1]).
false.
Метки: ,