代码之家 › 专栏 › 技术社区 › Sam

如何在Swi Prolog中对元组列表排序

prolog-setof prolog

1

Sam · 技术社区 · 7 年前

我在swi prolog中有这样一个列表:

[(5,4), (1,4), (3,12), (4,2), (5,4)]

我需要将列表按每个“tuple”的第二个元素进行组织,删除任何重复的元素,因此此列表如下所示:

[(4,2), (1,4), (5,4), (3,12)]

使用谓词sort/2,它可以完成我想要的一切,除了它根据每个元组的第一个元素进行组织之外,我不希望这样。

我该怎么做?

2 回复 | 直到 7 年前

1

Daniel Marques 7 年前

灵感来自 http://kti.mff.cuni.cz/~bartak/prolog/sorting.html ,我修改了pivot算法以满足您的需要。我在Sicstus Prolog上进行了测试,效果很好。

:- use_module(library(lists)).

pivoting(_,[],[],[]).
pivoting((A,B),[(C,D)|T],[(C,D)|L],G):-D>B,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],[(C,D)|L],G):-D=B,C>A,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,[(C,D)|G]):-D<B,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,[(C,D)|G]):-D=B,C<A,pivoting((A,B),T,L,G).
pivoting((A,B),[(C,D)|T],L,G):-A=C,D=B,pivoting((A,B),T,L,G).

quick_sort(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
    pivoting(H,T,L1,L2),
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted).

2

1

Isabelle Newbie 7 年前

如果您不想编写自己的排序例程(Prolog的排序可能比您的更优化),那么可能会有一些特定于实现的谓词,您可以使用它们来比较您的选择。

例如,SWI Prolog具有 predsort/3 它采用谓词进行排序。您可以将其与一个谓词一起使用,该谓词首先对一对中的第二个元素进行比较:

compare_by_second(<, (A, B), (C, D)) :-
    (   B @< D
    ;   B == D,
        A @< C ).
compare_by_second(=, (A, B), (C, D)) :-
    A == C,
    B == D.
compare_by_second(>, (A, B), (C, D)) :-
    (   B @> D
    ;   B == D,
        A @> C ).

% ?- predsort(compare_by_second, [(5,4), (1,4), (3,12), (4,2), (5,4)], Sorted).
%@ Sorted = [ (4, 2), (1, 4), (5, 4), (3, 12)] ;
%@ false.