Prolog最后一个元素函数返回整个列表

Question

我有一个在Prolog中实现快速排序的任务，然后返回最后一个元素。我让快速排序工作了，但是当它到达最后一个元素时，它返回整个列表。我的最后一个元素在单独运行时可以工作，但在快速排序结束时调用它时不行。有什么我需要改变的想法吗?

quicksort([],[]).
quicksort([H|T],Final) :- 
partition(T,H,Left,Right), 
quicksort(Left,Ls),                           
quicksort(Right,Rs), 
append(Ls,[H|Rs],Sorted), 
lastelement(Final, [Sorted]).
partition([],Pivot,[],[]).
partition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, partition(T,Pivot,Ls,Rs).
partition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, partition(T,Pivot,Ls,Rs).
append([],Sorted,Sorted).
append([H|T],Sorted,[H|Z]) :- append(T,Sorted,Z).
lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).

Answer 1

正如@gusbro所观察到的，不可能定义一个递归谓词，其基case生成一个列表，其递归步骤产生一个元素。因此，一个可能的解决方案是:

quicksort([],[]).
quicksort([H|T], Sorted) :-
mypartition(T, H, Left, Right),
quicksort(Left,  Ls),
quicksort(Right, Rs),
myappend(Ls, [H|Rs], Sorted).
mypartition([], _Pivot,[],[]).
mypartition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, mypartition(T,Pivot,Ls,Rs).
mypartition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, mypartition(T,Pivot,Ls,Rs).
myappend([], Sorted, Sorted).
myappend([H|T], Sorted, [H|Z]) :- myappend(T, Sorted, Z).
lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).
quicksort_last(List, Last) :-
quicksort(List, Sorted),
lastelement(Last, Sorted).

例子:

?- quicksort([61,46,59,27,12,38], S).
S = [12, 27, 38, 46, 59, 61] ;
false.
?- quicksort_last([61,46,59,27,12,38], S).
S = 61 ;
false.

一个更好的解决方案

quicksort_last/2的平均复杂度时间为O(n lgn)，假设解必须基于快速排序的思想，一个更高效的方法，平均复杂度时间O(n)为:

• 要有最后一项(即最大项)，完整排序列表不能为空。
• 分区后:
  • 如果右子列表为空，则Pivot是完整排序列表中的最后一个元素(因为Pivot更大)小于左子列表中的所有元素)。
  • 否则，右子列表中的最后一个元素也是完整排序列表中的最后一个元素(因为，如果右子列表中至少有一个项目，则Pivot更小比它)。

quick_last([Pivot|Rest], Last) :-
mypartition(Rest, Pivot, _, Right),
(   Right = []
->  Last = Pivot
;   quick_last(Right, Last) ).

例子:

?- quick_last([61,46,59,27,12,38], S).
S = 61 ;
false.
?- quick_last([71, 100, 83, 97, 62, 6, 42, 3, 40], L).
L = 100 ;
false.

在最好的情况下，每次递归调用quick_last/2时，列表的长度除以2。由于partition/4消耗的时间与列表的长度成正比，我们有T(n) = n + n/2 + n/4 +…+ 1≈2*n.

评论>这个解决方案是在无序列表中查找k最小元素的算法的特殊情况(参见:quick-select)。

Answer 2

lastElement/2似乎试图从排序列表中找到最后一个元素…并在各种递归调用中将其作为列表本身传递回来。例如，调用quicksort(Left,Ls)时，好像Ls将是Left的排序版本，但它实际上返回该列表的最后一个元素。

如果你想要最后一个元素，当然，你可以这样做，但你可以在快速排序之后得到它。(当然，也可以用别的方法找到它。)

quicksort([H|T],Sorted) :- partition(T,H,Left,Right), 
quicksort(Left,Ls),
quicksort(Right,Rs), 
append(Ls,[H|Rs],Sorted).
findLastElement(List,Final) :- quicksort(List,Sorted), lastelement(Final, Sorted).