我正在尝试按照给定的优先顺序对颜色列表进行排序。例如,按此顺序 [z,b,g,r,w] 排序的列表 [r,z,z,w,g,g,r,z] 将给出 [z,z,z, g,g,r,r,w].
我尝试使用基本的冒泡排序算法并添加检查以查看前两个术语中的哪一个在顺序列表中“更高”。
% take the to-sorted list, the order in which to sort the list, and the
% result.
%colourSort([r,z,z,w,g,g,r,z],[z,b,g,r,w],X). returns X = [z,z,z,g,g,r,r,w]
colourSort(List,Order,Sorted):-
swap(List,List1,Order),
!,
colourSort(List1,Order,Sorted).
colourSort(Sorted,_,Sorted).
% check if the either the first or second letter is first in the order
% list, if neither check the next letter in the order list.
check(A,_,[H|_],A):-
A == H.
check(_,B,[H|_],B):-
B == H.
check(A,B,[_|T],R):-
check(A,B,T,R).
check(_,_,[],_).
%swap incase a set of letters isn't ordered, continues otherwise.
swap([X,Y|Rest],[Y,X|Rest],Order):-
check(X,Y,Order,R),
X == R.
swap([Z|Rest],[Z|Rest1],Order) :-
swap(Rest,Rest1,Order).
当我运行代码时,它最终导致我的 swi-prolog 崩溃,我假设它陷入了循环或其他问题,但一直无法弄清楚原因或方式。
如有任何建议或提示,我们将不胜感激。
最佳答案
这是针对所述问题的解决方案,但是,该解决方案并未使用自定义排序算法。相反,它使用常见的 pairs数据结构(使用 (-)/2
运算符形成项目列表 Key-Value
)和用于排序的 keysort/2
. 编辑:此答案已根据@mat 在评论中的提示进行了修改,并提供了更简洁的解释)。
解决方法:
item_with_rank(Ranking, Item, Rank-Item) :-
nth0(Rank, Ranking, Item).
sort_by_ranking(Ranking, ToSort, Sorted) :-
maplist(item_with_rank(Ranking), ToSort, Ranked),
keysort(Ranked, RankedSorted),
pairs_values(RankedSorted, Sorted).
解释:
我们定义了一个谓词 item_with_rank(Ranking, Item, Rank-Item)
,它使用任意排序的术语列表作为 Ranking
,并与给定的 Item
一个 Rank
,相当于 Ranking
中第一项从 0 开始的索引,与 Item
统一。然后我们定义 sort_by_ranking(Ranking, ToSort, Sorted)
。 sort_by_ranking/3
使用 maplist/3
调用 item_with_rank/3
,给定 Ranking
,在每个元素上列表 ToSort
,获取对列表,Ranked
,为每个项目分配一个排名。我们使用 keysort/2
对 Ranked
进行排序,以便它们的元素顺序与它们在 RankedSorted
中的“等级”(键)的值一致.当我们只从 RankedSorted
中提取值时,我们剩下的是 Sorted
项,这就是我们想要的:
使用示例:
?- sort_by_ranking([z,b,g,r,w], [r,z,z,w,g,g,r,z], S).
S = [z, z, z, g, g, r, r, w] ;
false.
关于list - Prolog:按替代索引对列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29156116/