Удаление дубликатов при поддержании порядка в Прологе - PullRequest
Новая
       44

Удаление дубликатов при поддержании порядка в Прологе

1 голос
/ 23 апреля 2020

Я пытаюсь создать предикат, который удаляет дубликаты из списка, сохраняя его относительный порядок. Например, список [1,2,2,3,4,5,5,2] должен возвращать [1,2,3,4,5]. Тем не менее, мой код может удалить только последовательные дубликаты и, например, не 2 в конце. 

remove_duplicates([],[]).
remove_duplicates([H],[H]).
remove_duplicates([H,H|T],[H|List]) :- remove_duplicates(T,List).
remove_duplicates([H,X|T],[H|T1]):- X\=H, remove_duplicates([X|T],T1).

Другим подходом, о котором я думал, было использование члена, чтобы увидеть, содержит ли Хвост Голову. Тем не менее, я могу думать только о том, чтобы решить эту проблему, когда я уберу голову, если голова - это член хвоста. Это, однако, сохранит только последний экземпляр числа и нарушит относительный порядок чисел в списке.

Например: 

[1,2,2,3,4,5,5,2] 
[1,3,4,5,2]

Когда я действительно хочу 

[1,2,3,4,5]

1 Ответ

1 голос
/ 24 апреля 2020

Вы можете использовать аккумулятор: дополнительный параметр, здесь список, который изначально пуст и при появлении новых элементов будет расти. Каждый рекурсивный вызов списка передается (или обновляется копия).

Например: 

remove_duplicates(LA, LB) :-
    remove_duplicates(LA, LB, <b>[]</b>).

remove_duplicates([], [], <b>_</b>).
remove_duplicates([H|T], R, <b>Seen</b>) :-
    (  member(H, Seen)
    -> (R = S, <b>Seen1 = Seen</b>)
    ;  (R = [H|S], <b>Seen1 = [H|Seen]</b>)
    ),
    remove_duplicates(T, S, <b>Seen1</b>).

Это дает нам: 

?- remove_duplicates([1,2,2,3,4,5,5,2], L).
L = [1, 2, 3, 4, 5].

Конечно, вы можете использовать более эффективные структуры данных, чем список. Я оставляю это как упражнение.

...