在Prolog中的元组列表中按降序排序

Question

我想基于列表的第二个值按降序对元组列表进行排序,而不使用内置的排序谓词.

示例:(Name, Age).

unsorted_list = [(mary, 20), (jack, 50), (bob, 16), (bill, 20) ].

sorted_list = [(jack, 50), (bill, 20), (mary, 20), (bob, 16)].

有谁知道这样做的优雅方式？

Answer 1

有很多方法可以实现这一点.一种方法是从头开始实现您的自定义对排序,这样做的好处是您可以确切地知道算法的实现以及复杂性,但这可能不是那么优雅.

另一种更优雅的方法是使用Prolog的ISO谓词keysort/2,它对表单对的列表进行[X1-Y1, X2-Y2, ...]排序,并且排序基于pair(Xi)的第一个参数.所以你需要在表格中更改你的清单[-20-mary, -50-jack, -16-bob, -20-bill]然后申请keysort/2.请注意,由于@ false的注释为了实现降序的稳定解决方案,我们可以否定数字并按升序排序否定数字:

:-use_module(library(clpfd)).

swap_internals((X,Y), Y1-X):- Y1 #= -Y.

pair_sort(L,Sorted):- 
      maplist(swap_internals, L, L2),
      keysort(L2, L3),
      maplist(swap_internals, Sorted, L3).

在上面,您使用maplist/3和以适当的形式构建列表,对其进行swap_internals/2排序keysort/2,然后再次使用它进行更改maplist/3.

例:

   ?- pair_sort([(mary, 20), (jack, 50), (bob, 16), (bill, 20) ],L).
    L = [(jack, 50),  (bill, 20),  (mary, 20),  (bob, 16)].

这是降序的另一种方式,只需使用sort/4谓词:

sort(2, @>=, L, Sorted).

例:

?- sort(2,@>=, [(mary, 20), (jack, 50), (bob, 16), (bill, 20) ], L).
L = [(jack, 50),  (mary, 20),  (bill, 20),  (bob, 16)].

虽然它不是ISO谓词,但这种方式显然更容易.

编辑

我没有看到"没有使用内置排序谓词"部分问题,所以你可以编写一个典型的合并排序来改变merge/2下面的第3条规则以处理对:

halve([], [], []).
halve([A], [A], []).
halve([A,B|Cs], [A|X], [B|Y]) :- halve(Cs, X, Y).

merge([], Ys, Ys).
merge(Xs, [], Xs).
merge([(X1,X2)|Xs], [(Y1,Y2)|Ys], M) :-
   (  
      X2 > Y2 -> M = [(X1,X2)|Ms], merge(Xs, [(Y1,Y2)|Ys], Ms) 
    ; M = [(Y1,Y2)|Ms], merge([(X1,X2)|Xs], Ys, Ms) 
   ).

mergeSort([], []).
mergeSort([E], [E]).
mergeSort([E1,E2|Es], SL) :- 
     halve([E1,E2|Es], L1, L2),
     mergeSort(L1, SL1),
     mergeSort(L2, SL2),
     merge(SL1, SL2, SL). 

例:

?- mergeSort([(mary, 20), (jack, 50), (bob, 16), (bill, 20) ],L).
L = [(jack, 50),  (bill, 20),  (mary, 20),  (bob, 16)] ;
false.