有很多关于如何删除重复和类似问题的资源,但我似乎无法找到任何关于删除独特元素的资源。我正在使用 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
来改进它当我们找到多个元素但最坏情况仍然是 O(n)
时.那么我们来到
remove_unique
.对于每个元素,我们检查当前元素是否 is_unique
在 O
.如果测试失败,该元素将被添加到下一个分支的结果列表中。正在运行O(n²)
,我们得到了很多推论。虽然我认为我们不能在最坏的情况下加快速度,但我们能比这种幼稚的解决方案做得更好吗?我能清楚看到的唯一改进是更改 count
一旦识别出>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).
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
关于list - 仅删除唯一元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15990666/