有很多关于如何删除重复项和类似问题的资源,但我似乎无法找到任何有关删除唯一元素的资源。我正在使用 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
is O(n)
也是如此is_unique
因为它只是使用count
。我可以通过以下方式改进这个fail
当我们找到多个元素但最坏情况仍然是O(n)
.
那么我们来到remove_unique
。对于每个元素,我们检查当前元素是否is_unique
in O
。如果测试失败,该元素将被添加到下一个分支的结果列表中。运行O(n²)
,我们得到很多推论。虽然我认为在最坏的情况下我们无法加快速度,但我们能比这个简单的解决方案做得更好吗?我能清楚地看到的唯一改进就是改变count
一旦识别出 >1 个元素就会失败。