prolog - Prolog差异列表 - 合并排序

Question

我必须编写谓词，它将一个列表分成两个列表（减半）：

halve(X-Y, X-Z, Z-Y) :- halve_pom(X-Y, X-Y, Z), !.

halve_pom(Z-Y, Y-Y, Z).

halve_pom([_|A]-Y, [_,_|B]-Y, Z) :- halve_pom(A-Y, B-Y, Z).

这很容易，但现在我必须编写能够进行归并排序的算法——我不知道。该算法必须使用差异列表。

请帮忙。

Answer 1

不，这并不“容易”，因为它不起作用，不幸的是。halve([1,2,3]-[],A,B)不工作；halve_pom([1,2,3]-[],A,B)也不行。此外，尚不清楚您更喜欢哪种拆分方案，[1,2,3,4,5,6,7] -> ([1,3,5,7] , [2,4,6])或者-> ([1,2,3,4] , [5,6,7]).

如果您的halve谓词有效，那么您剩下要做的就是定义merge，它将按顺序合并列表的两半。然后，

mergesort(A,S):- halve(A,B-[],C-[]), mergesort(B,SB), mergesort(C,SC),
  merge(SB,SC,S-[]).

请注意，您可能会使用普通列表调用它A，即halve谓词应该将其第一个参数视为普通列表（即不是差异列表）。

另请参阅Prolog 中处理列表时的“-”符号是什么意思？. '-'是不必要的；相反，它的两个成分应该用作谓词的两个独立参数。

---

所以，一种编码方式halve是

halve([A,B|C],[A|X]-ZX,[B|Y]-ZY):- halve(C,X-ZX,Y-ZY). 
halve([A],[A|X]-X,Y-Y). 
halve([],X-X,Y-Y).

相同的方法可用于编码merge：

merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A=<C, S=[A|T], merge(B,SC,T-Z).
merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A>C,  ... ,    ... .
merge(SB,SC,S-Z):- SB=[A|B], SC=[],          ... ,    ... .
merge(SB,SC,S-Z):- SB=[], SC=[C|D],          S=[C|T], ... .
merge([],[],Z-Z).