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

Question

Существует много ресурсов по удалению дубликатов и аналогичных проблем, но я не могу найти их при удалении уникальных элементов. Я использую 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. Я мог бы улучшить это на fail ing, когда мы найдем несколько элементов, но в худшем случае все еще O(n).

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

Answer 1

Использование 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 

Answer 2

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

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