仅删除唯一元素 [英] Remove unique elements only

问题描述

关于如何删除重复项和类似问题，有很多资源，但是我似乎找不到关于删除唯一元素的任何资源.我正在使用SWI-Prolog，但是我不想使用内置的插件来实现此目的.

There are many resources on how to remove duplicates and similar issues but I can't seem to be able to find any on removing unique elements. I'm using SWI-Prolog but I don't want to use built-ins to achieve this.

也就是说，调用remove_unique([1, 2, 2, 3, 4, 5, 7, 6, 7], X).应该会很高兴地导致X = [2, 2, 7, 7].

That is, calling remove_unique([1, 2, 2, 3, 4, 5, 7, 6, 7], X). should happily result in X = [2, 2, 7, 7].

显而易见的解决方案是按照

The obvious solution is as something along the lines of

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.当我们发现多个元素但最坏的情况仍然是O(n)时，我可以通过fail ing来改善此问题.

It should become quickly apparent why this isn't an ideal solution: count is O(n) and so is is_unique as it just uses count. I could improve this by failing when we find more than one element but worst-case is still O(n).

所以我们来看看remove_unique.对于每个元素，我们检查是否O中的当前元素is_unique.如果测试失败，则该元素将添加到下一个分支的结果列表中.在O(n²)中运行，我们得到了很多推论.虽然我认为在最坏的情况下我们无法加快速度，但是我们能比这种天真的解决方案做得更好吗?我能清楚看到的唯一改进是，一旦识别出> 1个元素，就将count更改为失败的东西.

So then we come to remove_unique. For every element we check whether current element is_unique in O. If the test fails, the element gets added to the resulting list in the next branch. Running in O(n²), we get a lot of inferences. While I don't think we can speed it in the worst case, can we do better than this naïve solution? The only improvement that I can clearly see is to change count to something that fails as soon as >1 elements are identified.

推荐答案

与 tpartition/4 配合使用 if_/3 和 ，我们这样定义remove_unique/2:

Using tpartition/4 in tandem with if_/3 and (=)/3, we define remove_unique/2 like this:

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).

这是OP给出的示例查询:

Here's the sample query, as given by the OP:

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

这篇关于仅删除唯一元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！