5

我正在尝试创建一个函数，将可变长度列表按顺序拆分为三个偶数长度列表。以下将其拆分为三个，但进程一次将它们插入每个列表中。

我想要的一个例子是：

[1, 2, 3, 4, 5] -> [1, 2], [3, 4], [5]

另一个例子是：

[8, 7, 6, 5, 4, 3, 2, 1] -> [8, 7, 6], [5, 4, 3], [2, 1].

以下代码通过一次插入每个列表来拆分它们：

div([], [], [], []).
div([X], [X], [], []).
div([X,Y], [X], [Y], []).
div([X,Y,Z|End], [X|XEnd], [Y|YEnd], [Z|ZEnd]):-
  div(End, XEnd, YEnd, ZEnd).

此代码输出：

[1, 2, 3, 4, 5] -> [1, 4], [2, 5], [3]

我该如何解决这个问题？

4

2 回答 2

5

当第一个参数列表的长度未知时，@Boris 的答案不会终止。要看到这一点，无需再看第一个带有的目标：

格（L，L1，L2，L3）：-
    length(L, Len), false ,
     % 在这里你计算例如 Len1 和 Len2 
    length(L1, Len1) ,
     length(L2, Len2) ,
     append(L1, L1_suffix, L) ,
     append(L2, L3, L1_suffix)。

另一方面，您的原始程序具有非常好的终止属性。cTI 给出了以下最佳终止属性：

div(A,B,C,D) terminates_if b(A);b(B);b(C);b(D).

换句话说，为了确保终止，您只需要一个参数（或者AorB或Cor D）作为一个具体的列表，它是有限的和接地的（这就是b(..)意思）。这是一个非常强的终止条件。论据不符，真是太可惜了！为什么不概括您的程序？它唯一的问题是它限制了列表元素。所以我将列表元素的所有变量名替换为_s：

gdiv([], [], [], []).
gdiv([_], [_], [], []).
gdiv([_,_], [_], [_], []).
gdiv([_,_,_|End], [_|XEnd], [_|YEnd], [_|ZEnd]):-
  gdiv(End, XEnd, YEnd, ZEnd).

该程序具有完全相同的终止属性。

唉，现在有点太笼统了。Boris 的解决方案现在可以重新利用：

divnew(Zs, As, Bs, Cs) :-
   gdiv(Zs, As, Bs, Cs),
   append(As, BsCs, Zs),
   append(Bs, Cs, BsCs).

我更喜欢的表达方式是：

divnew(Zs, As, Bs, Cs) :-
   gdiv(Zs, As, Bs, Cs),
   phrase( ( seq(As), seq(Bs), seq(Cs) ), Zs).

有关的定义，请参见其他答案seq//1。

于 2016-04-07T14:17:02.430 回答
2 
div(L, L1, L2, L3) :-
    append(L1, L1_suffix, L),
    append(L2, L3, L1_suffix).

你看到这是如何拆分三个列表的吗？现在您没有说您希望列表L1、L2和多长时间L3。如果您不希望谓词像现在一样通用，您可以使用length/2来获取和设置三个结果的长度。L

既然你说“相对均匀长度”，这是相对的，我需要以某种方式解释它，假设你的意思是，对于正整数 len 和 n，len = 3n，你得到 len1 = len2 = len3 = n，对于 k = 3n+1 你得到 len1 = n+1, len2 = len3 = n, 对于 k = 3n+2 你得到 len1 = len2 = n+1, len3 = n。我让你弄清楚如何计算长度。

div(L, L1, L2, L3) :-
    length(L, Len),
    % here you compute for example Len1 and Len2
    length(L1, Len1),
    length(L2, Len2),
    append(L1, L1_suffix, L),
    append(L2, L3, L1_suffix).
于 2014-11-21T09:20:12.217 回答