Prolog的排序列表使用的排序方法

Question

sort([ [30,100], [10,11] ], X). 

得到

X = [[10,11],[30,100]] 

我如何排序只能通過每個子列表的第一個指數？

即

X = [[10,100], [30, 11]] 

感謝

Answer 1

下面是我未經測試的代碼..有可能是一/二化妝錯誤...輸入列表是基於該頭價值分成兩列表和結果兩個列表遞歸處理，最終得到排序的輸出。

sort(Input,Output):-sort(Input,[],Output). 

sort([],SortedOut,SortedOut). 
sort([[Index1,Index2]|Tail],SortedBig,Out):- 
    split(Tail,[Index1,Index2],LessList,BigList), 
    !,sort(BigList,SortedBig,NewSort), 
    sort(LessList,[[Index1,Index2]|NewSort],Out). 

split([],[_D],[],[]). 
split([[Index1,Index2]|Rem],[Index21,Index22],[[Index1,Index1]|L1],L2):- 
    Index1<Index21, 
    !,split(Rem,[Index21,Index22],L1,L2). 
split([[Index1,Index2]|Rem],[Index21,Index22],L1,[[Index1,Index1]|L2]):- 
    !,split(Rem,[Index21,Index22],L1,L2). 

試試這個，讓我知道...

Answer 2

型的簡單方法應當仔細閱讀可用建宏。然後在第一個元素從各個子表，對它們進行排序，並在原有的替換：

sortfirst(L, S) :- 
    maplist(get_first, L, A), 
    msort(A, B), 
    maplist(set_first, L, B, S). 

get_first([E|_], E). 
set_first([_|R], E, [E|R]). 

編輯：注意，要求msort，以避免失去重複。

測試：

?- sortfirst([ [30,100], [10,11] ], X). 
X = [[10, 100], [30, 11]]. 

的get/set第一隻是需要從MAPLIST調整參數：如果我們使用lambda，我們可以寫一個真正的 '一個內膽' 過程：

:- [lambda]. 

sortfirst_lambda(L, S) :- 
    maplist(\X^Y^(X = [E|_], Y = E), L, A), 
    msort(A, B), 
    maplist(\X^Y^Z^(X = [_|R], Y = E, Z = [E|R]), L, B, S). 

簡單的身份可以簡化一些表達式：

sortfirst_lambda(L, S) :- 
    maplist(\X^Y^(X = [Y|_]), L, A), 
    msort(A, B), 
    maplist(\X^Y^Z^(X = [_|R], Z = [Y|R]), L, B, S). 

編輯：或者更簡單：

sortfirst_lambda(L, S) :- 
    maplist(\[Y|_]^Y^true, L, A), 
    msort(A, B), 
    maplist(\[_|R]^Y^[Y|R]^true, L, B, S). 

在這裏你可以看到，在原來的GET /先設置，需要的參數，就統一。

因此拉姆達它的語法方便，但有代價的：

?- randomlists(100000, 3, -30,+30, L), 
time(sortfirst(L,A)), 
time(sortfirst_lambda(L,B)), 
assertion(A=B). 

% 400,012 inferences, 0,482 CPU in 0,483 seconds (100% CPU, 830072 Lips) 
% 1,700,012 inferences, 1,717 CPU in 1,721 seconds (100% CPU, 990302 Lips) 
L = [[-8, -13, 11], [-13, -27, -29], [5, 10, -24], [-8, -7, -6], [3, -24, -9], [-13, -20, -24], [7, 27|...], [-5|...], [...|...]|...], 
A = B, B = [[-30, -13, 11], [-30, -27, -29], [-30, 10, -24], [-30, -7, -6], [-30, -24, -9], [-30, -20, -24], [-30, 27|...], [-30|...], [...|...]|...]. 

這裏的服務謂詞建立大小的測試數據：

randomlist(Length, Low, High, List) :- 
    findall(E, (between(1, Length, _), 
      random(Low, High, E)), List). 

randomlists(Length1, Length2, Low, High, ListOfLists) :- 
    findall(E, (between(1, Length1, _), 
      randomlist(Length2, Low, High, E)), ListOfLists). 

Answer 3

@chac（+1 BTW）：有沒有需要拉姆達到一行這個（在swi中至少有！）：

sortfirst(L, Res) :- 
    maplist(selectchk, X, L, R), 
    msort(X, XS), 
    maplist(selectchk, XS, Res, R). 

但是lambda版本或者你的第一個ve我認爲rsion不那麼棘手，可讀性更強。