Удалить дубликаты из списка, но не возвращать два одинаковых результата в SWI-Prolog? - PullRequest
Новая
       18

Удалить дубликаты из списка, но не возвращать два одинаковых результата в SWI-Prolog?

0 голосов
/ 13 марта 2019 
duplicate([],[]).
duplicate([A|B],[A|B1]) :- not(member(A,B)), duplicate(B,B1).
duplicate([A|B],List) :- member(A,B), duplicate(B,List).

Я написал этот предикат для удаления дубликата из списка, но когда я проверяю его, 

?- duplicate([a,b,c,a,d,c,b,a,e,f],N).
N = [d, c, b, a, e, f] ;
N = [d, c, b, a, e, f] ;
false.

Можно ли сохранить только один результат, а не два одинаковых?(поэтому он вернет только один список).

Кроме того, мне не разрешено использовать операторы, которые изменяют поиск в обратном направлении, такие как оператор сокращения!, операторы отрицания не +, или оператор if-then-почти оператор с -> и;

Был бы признателен, если бы кто-то мог мне помочь.: D

Ответы [ 2 ]

2 голосов
/ 13 марта 2019

Фактическая причина получения более одного ответа - цель member(A,As).Он выдает несколько ответов для дубликатов в As. 

?-  member(a, [a,a]).
    true
;   true.

. Есть несколько выходов.

memberchk/2 или once/1

memberchk/2 определяетсяas 

memberchk(X, Xs) :-
   once(member(X, Xs)).

Это удаляет альтернативные ответы.Но тогда это может удалить и другие действительные решения тоже.Подумайте: 

?-        memberchk(X, [a,b]), b = X.
false.
?- b = X, memberchk(X, [a,b]), b = X.
b = X.

Так что memberchk/2 чувствителен к точному воплощению, что делает его очень хрупким, нечистым предикатом.

Но у него есть один хороший момент: он придерживается только одногоответ за 

?- memberchk(a, [a,a]).
true.

Итак, что было бы идеально, так это определение, которое является одновременно чистым и соответствует первому элементу.Введите

memberd/2

memberd(X, [X|_Ys]).
memberd(X, [Y|Ys]) :-
   dif(X, Y),
   memberd(X, Ys).

В этом определении рекурсивное правило имеет значение только в том случае, если элемент списка отличается.Таким образом, это правило никогда не будет применяться к memberd(a, [a,a,a]).

Еще одна проблема в вашем определении - not(member(A,B)), которая ведет себя только так, как задумано, если A и B достаточно созданы.Ваше определение не подходит для: duplicate([a,X],[a,b])., хотя есть решение: X = b.

Вместо этого замените его на non_member/2.

В качестве альтернативы, если вызаинтересованы в наиболее эффективном решении, рассмотрим library(reif) для SICStus и SWI , что приводит к: 

list_nub([], []).
list_nub([X|Xs], Ys0) :-
   if_(memberd_t(X, Xs),  Ys0 = Ys1, Ys0 = [X|Ys1]),
   list_nub(Xs, Ys1).
0 голосов
/ 13 марта 2019

Вот один способ удалить все дубликаты, не самый эффективный, но я думаю, что это довольно легко понять намерение. 

rm_duplicates(In, Out) :-
    exclude(has_duplicate(In), In, Out).

has_duplicate(List, Case) :-
    dif(I, J),
    nth0(I, List, Case),
    nth0(J, List, Case).

Если вы хотите сделать список в наборе: 

list_to_set(List, Set).

Документально подтверждено: list_to_set / 2

...