4

有很多关于如何删除重复和类似问题的资源，但我似乎无法找到任何关于删除独特元素的资源。我正在使用 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).

应该很快就会明白为什么这不是一个理想的解决方案：countis O(n)and so is is_uniqueas it just uses count. fail当我们找到多个元素但最坏的情况仍然是 时，我可以通过 ing 来改进这一点O(n)。

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

4

2 回答 2

3

与andtpartition/4一起使用 ，我们定义如下：if_/3(=)/3remove_unique/2

删除唯一（[]，[]）。
remove_unique([E|Xs0], Ys0) :-
   tpartition ( = (E), Xs0, Es, Xs),
    if_ (Es = [], Ys0 = Ys, append ([E|Es], Ys, Ys0)),
   remove_unique(Xs, Ys)。

这是 OP 给出的示例查询：

?- remove_unique([1,2,2,3,4,5,7,6,7], Xs). 
Xs = [2,2,7,7].                       % succeeds deterministically
于 2015-08-04T09:12:11.963 回答
1

只要您不知道列表以任何方式排序，并且您想保持非唯一元素的顺序，在我看来您无法避免进行两次传递：首先计算出现次数，然后选择只有重复的元素。

如果您使用（自平衡？）二叉树在第二遍期间计算出现次数和查找怎么办？绝对不是 O(n²)，至少...

于 2013-04-13T20:28:08.783 回答