Удалить только уникальные элементы

Существует много ресурсов о том, как удалить дубликаты и подобные проблемы, но я не могу найти ни одного по удалению уникальных элементов. Я использую SWI-Prolog, но не хочу использовать встроенные модули для достижения этой цели.

То есть вызов remove_unique([1, 2, 2, 3, 4, 5, 7, 6, 7], X). должен с успехом привести к X = [2, 2, 7, 7].

Очевидным решением является что-то вроде

count(_, [], 0) :- !.
count(E, [E | Es], A) :-
  S is A + 1,
  count(E, Es, S).
count(E, [_ | Es], A) :-
  count(E, Es, A).

is_unique(E, Xs) :-
  count(E, Xs, 1).

remove_unique(L, R) :- remove_unique(L, L, R).
remove_unique([], _, []) :- !.
remove_unique([X | Xs], O, R) :-
  is_unique(X, O), !,
  remove_unique(Xs, O, R).
remove_unique([X | Xs], O, [X | R]) :-
  remove_unique(Xs, O, R).

Должно сразу стать понятно, почему это не идеальное решение: count — это O(n), как и is_unique, так как он просто использует count. Я мог бы улучшить это с помощью failing, когда мы находим более одного элемента, но в худшем случае все еще O(n).

Итак, мы подошли к remove_unique. Для каждого элемента мы проверяем, является ли текущий элемент is_unique в O. Если тест не пройден, элемент добавляется в результирующий список в следующей ветке. Работая в O(n²), мы получаем много выводов. Хотя я не думаю, что мы сможем ускорить его в худшем случае, можем ли мы добиться большего, чем это наивное решение? Единственное улучшение, которое я ясно вижу, - это изменить count на что-то, что дает сбой, как только идентифицируется >1 элемент.


list prolog prolog-dif
person Mateusz Kowalczyk    schedule 13.04.2013    source источник
comment
Вы можете сначала отсортировать (O (N * log (N))), а затем удалить уникальные элементы (O (N)) и после этого использовать двоичный поиск или кучу для каждого элемента, чтобы определить, является ли он уникальным O (N * log ( Н))   -  person User    schedule 13.04.2013

Ответы (2)


arrow_upward
3
arrow_downward

Использование tpartition/4 в тандеме с if_/3 и (=)/3 мы определяем remove_unique/2 следующим образом:

remove_unique([], []).
remove_unique([E|Xs0], Ys0) :-
   tpartition(=(E), Xs0, Es, Xs),
   if_(Es=[], Ys0 = Ys, append([E|Es], Ys, Ys0)),
   remove_unique(Xs, Ys).

Вот пример запроса, заданный ОП:

?- remove_unique([1,2,2,3,4,5,7,6,7], Xs). 
Xs = [2,2,7,7].                       % succeeds deterministically
person repeat    schedule 04.08.2015

arrow_upward
1
arrow_downward

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

Что, если вы используете (самобалансирующееся?) бинарное дерево для подсчета вхождений и поиска во время второго прохода? Определенно не O(n²), по крайней мере...

person Community    schedule 13.04.2013
comment
Хорошее предложение, +1! Также ознакомьтесь с красивой версией list_to_set/2 Ульриха Ноймеркеля, использующей сортировку и унификацию для эффективного обнаружения повторяющихся элементов: git commit. - person mat; 04.08.2015