Пролог: проверка дубликатов в списке

  1. Напишите предикат allDistinct/1, параметром которого является список (символов) и который успешен, если все символы в списке различны.

    notin(A,[]).
notin(A,[B|C]) :-
   A\=B,
   notin(A,C).

allDistinct([]).
allDistinct([_]).
allDistinct([A|B]) :-
   notin(A,B), 
   allDistinct(B).

list prolog prolog-dif
person LRAC    schedule 08.03.2016    source источник
comment
allDistinct(B) говорит, что любой список различен! И... пожалуйста, укажите, в чем вам нужна помощь. Вы не задали вопрос.   -  person lurker    schedule 09.03.2016
comment
Помимо вызова allDistinct(B) без отступа, я не понимаю, почему этот код не должен работать. предложение allDistinct([_]) также кажется избыточным.   -  person Raivo Laanemets    schedule 11.03.2016

Ответы (3)


arrow_upward
5
arrow_downward

Следуя предыдущему эскизу @whd, мы можем действовать следующим образом.

На основе iwhen/2 мы можем кратко определить distinct/1 следующим образом:

:- use_module(library(lists), [same_length/2]).

distinct(Es) :-
   iwhen(ground(Es), (sort(Es,Fs),same_length(Es,Fs))).

Примеры запросов с использованием SICStus Prolog 4.5.0:

| ?- distinct([1,2,3]).
yes
| ?- distinct([1,2,3.0]).
yes
| ?- distinct([1,2,3.0,2]).
no
| ?- distinct([1,2,3.0,X]).
! error(instantiation_error,_283)
person repeat    schedule 09.03.2016

arrow_upward
4
arrow_downward

Предикат sort/2 сортирует и удаляет дубликаты из списка. Вы можете использовать его, сравните длину (предикатlength/2) нового отсортированного списка со старым, если они отличаются, были некоторые повторяющиеся значения.

person whd    schedule 09.03.2016
comment
Напрямую, s(X). Но также обеспечьте достаточное количество экземпляров! - person repeat; 09.03.2016

arrow_upward
0
arrow_downward

Это один из тех вопросов, у которого имеется достаточное количество альтернативных разумных решений. Предполагая, что можно использовать общие библиотечные предикаты, вот еще один:

all_distinct(List) :-
    \+ (
        select(Element, List, Tail),
        select(Element, Tail, _)
    ).

Преимущество этого решения в производительности заключается в том, что оно прекращает сканирование списка, как только находит повторяющийся элемент. Но быстрее ли это, чем решения, основанные на стандартном предикате sort/2? Unclear as sort/2 — высокооптимизированный предикат в большинстве систем Prolog. Кроме того, давайте не будем забывать, что, если мы не уверены, что все элементы списка связаны, мы должны быть в безопасности и проверить это (см. Ответ @repeat).

person Paulo Moura    schedule 09.03.2016