Блог

Главная - Вопросы по программированию - Удаляйте дубликаты, сохраняя порядок, Пролог

Удаляйте дубликаты, сохраняя порядок, Пролог

#prolog

Вопрос:

 removeDup([],[]).
removeDup([H|T],T1) :- member(H,T), removeDup(T,T1).
removeDup([H|T],T1) :- not(member(H,T)), removeDup(T,Q), append(T1,[H],Q).

Это удаляет дубликаты, но изменяет порядок. Для добавления я ожидаю, что H будет добавлен в конец T1, а затем установлен как Q.

Как я могу сохранить заказ?

Предполагаемое поведение:

 ?- removeDup([1,2,3,2,4,5],X).
X = [1,2,3,4,5]

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

1. что-то не так с вашим третьим пунктом. Вы уверены, что используете именно эту программу?

Ответ №1:

 rmdup(Xs, Ys) :- rmdup1(Xs, Ys, []).

Вот Zs накопитель для не дублирующихся элементов списка. Если X есть Zs , проигнорируйте его, иначе внесите в список.

 rmdup1([], Ys, Zs) :- reverse(Ys, Zs).
rmdup1([X|Xs], Ys, Zs) :-
    member(X, Zs) -> rmdup1(Xs, Ys, Zs); 
    rmdup1(Xs, Ys, [X|Zs]).

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

1. Попробуйте listing(rmdup1) увидеть лучший стиль отступа для if-then-else

Ответ №2:

Я бы сделал что-то подобное:

 dedupe( Xs, Set ) :- dedupe_1(Xs, [], Set).

dedupe_1( []     , _    , []  ).
dedupe_1( [X|Xs] , Seen , Set ) :-
  ( member(X, Seen)
    ->    Set1  = Set
    ;  [X|Set1] = Set
  ),
  dedupe_1( Xs, [X|Seen], Set1 ).

Недостатком является то, что это обходится вам дорого с точки зрения используемого пространства. Вы можете избежать этого за счет a reverse/2 в конце:

 dedupe(Xs, Set) :- dedupe_1(Xs, [], Set).

dedupe_1( []     , Seen , Set ) :- reverse( Seen, Set).
dedupe_1( [X|Xs] , Seen , Set ) :-
  ( member(X,Seen)
    ->    Acc1  = Acc
    ;  [X|Acc1] = Acc
  ),
  dedupe_1( Xs, Acc1, Set).
Метки: , ,