找到列表中第K個最大元素的程序

Question

我正在爲kth_largest（Xs，K）編寫一個邏輯程序，該程序實現了用於查找列表Xs的第k個最大元素K的線性算法。該算法具有以下步驟：

1. 將列表分成五個元素的組。
2. 高效地找到每個組的中位數，這可以通過固定數量的 比較來完成。
3. 遞歸找到中位數。
4. 按照中位數的中位數對原始列表進行分區。
5. 遞歸地在適當的小列表中找到第k個最大元素。

我該怎麼辦？我可以從列表中選擇一個元素，但我不知道如何使用上述procedure.Here是我從列表

select(X; HasXs; OneLessXs) 
% The list OneLessXs is the result of removing 
% one occurrence of X from the list HasXs. 
select(X,[X|Xs],Xs). 
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs). 

Answer 1

我要跳，因爲選擇一個元素定義，以獲得最大的沒有人嘗試過答案，希望能夠對程序編制過程有所瞭解。

我發現維基百科文章Selection algorithm對於理解這種類型的「快速」（最壞情況線性時間）算法的大圖很有幫助。

但是你在問題結束時問的問題是一個稍微簡單的問題。你寫了「我怎麼去做？我可以從列表中選擇一個元素，但我不知道如何使用上述過程得到最大的。」 （強調加我）

現在似乎有一點混淆關於是否要實現「上述過程」，這是通過連續搜索中位數尋找第k個最大元素的一般配方，或者是否你問如何使用該配方來找到最簡單的元素（一種特殊情況）。請注意，該配方並未專門使用查找最大元素的方法來查找中位數或第k個最大元素。

但是，您給代碼在刪除該元素後找到列表元素和該列表的其餘部分，這是一個非確定性的謂詞，並允許通過列表的所有成員進行回溯。

查找最大元素的任務是確定性的（至少如果所有元素都是不同的），並且它比第k個最大元素（與其他事物相關的任務關聯的任務）的一般選擇更容易， 。

讓我們給一些簡單的，希望顯然是正確，代碼，找到最大的元素，然後談談做的更優化的方式。

maxOfList(H,[H|T]) :- upperBound(H,T), !. 
maxOfList(X,[_|T]) :- maxOfList(X,T). 

upperBound(X,[ ]). 
upperBound(X,[H|T]) :- 
    X >= H, 
    upperBound(X,T). 

這個想法應該是可以理解的。我們查看列表的頭部，並詢問該條目是否是列表其餘部分的上限。如果是這樣，那一定是最大值，我們完成了（削減使得它是確定性的）。如果沒有，那麼最大值後，必須在列表中出現，所以我們放棄了頭，繼續遞歸搜索是一個上限以後的所有元素的條目。切割是必不可少的在這裏，因爲我們必須爲了知道這是一個最大的原始列表的第一個這樣的條目停止。

我們已經使用了一個輔助謂詞upperBound/2，這並不罕見，但是這個實現的總體複雜度在列表長度上是最差的二次方。所以還有改進的餘地！

讓我暫停在這裏，以確保我不會完全偏離試圖解決您的問題。畢竟，你可能會想要問如何使用「上述過程」來找到最大的元素，所以我所描述的可能過於專業化。然而，它可能有助於理解一般選擇算法的聰明性，以瞭解簡單情況的微妙優化，找到最大元素。

補充：

直觀上我們可以發現，減少「所以 遠」通過列表中去，並跟蹤最大的價值在最壞的情況下 需要比較的次數。在程序語言中，我們可以通過重新指定變量的值來實現此目的，但Prolog不允許我們直接執行該操作。

而不是做這個的Prolog的方法是引入一個額外的參數和 界定謂詞maxOfList/2通過一個輔助謂詞 呼叫三個參數：

maxOfList(X,[H|T]) :- maxOfListAux(X,H,T). 

額外的論點maxOfListAux/3然後可用於跟蹤 最大值「到目前爲止」如下：

maxOfListAux(X,X,[ ]). 
maxOfListAux(Z,X,[H|T]) :- 
    (X >= H -> Y = X ; Y = H), 
    maxOfListAux(Z,Y,T). 

這裏maxOfListAux的第一個參數表示最後的答案，對於 列表中最大的元素，但我們不知道這個答案，直到我們 已經清空了列表。因此，這裏的第一個子句在這種情況下「確定」了答案 ，當列表的尾部達到 時，統一了第一個參數和第二個參數 （最大值「迄今」）。

爲maxOfListAux第二個子句離開第一個參數綁定和 「更新」的第二個參數作爲相應的列表 的下一個元素超過了先前的最大值或沒有。

這不是絕對必要在這種情況下使用輔助謂詞， 因爲我們可能會持續跟蹤使用列表，而不是額外的參數的 頭髮現的最大價值：

maxOfList(X,[X]) :- !. 
maxOfList(X,[H1,H2|T]) :- 
    (H1 >= H2 -> Y = H1 ; Y = H2), 
    maxOfList(X,[Y|T]).