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

Question

我有一项任务是在 Prolog 中实现快速排序，然后 return 最后一个元素。我有快速排序工作，但是当它到达最后一个元素时，将它称为 returns 整个列表。我的最后一个元素在运行单独工作时起作用，但在快速排序结束时调用它时不起作用。关于我需要更改的内容有什么想法吗？

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 所观察到的，无法定义其 基本情况 生成列表且其 递归步骤 生成的递归谓词一个元素。因此，一个可能的解决方案是：

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 lg n)。假设您的解决方案必须基于 快速排序 的想法，一种更高效的方法，使用平均复杂度时间 O(n)，为：

要有最后一项（又名，最大项），完整的排序列表不能为空。
分区后：
- 如果右子列表为空，则 Pivot 是完整排序列表中的最后一个元素（因为 Pivot 比 left[ 中的所有元素大 =55=] 子列表).

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.

REMARK 此解决方案是算法的一个特例，用于查找无序列表中的第 k 个最小元素（请参阅： quick-select).

Answer 2

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

如果你想要最后一个元素，当然，你可以做到，但你可以在完成快速排序后得到它。（当然也可以通过其他方式找到它。）

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

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

Prolog last element function returns whole list

prolog