使用 Prolog 按顺序将单个列表拆分为三个 [英] Splitting a single list into three in order using Prolog

问题描述

我正在尝试制作一个函数，将可变长度的列表按顺序拆分为三个偶数长度的列表.下面将其分为三部分，但进程将它们一次一个地插入到每个列表中.

我想要的一个例子是:

[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(结束，XEnd，YEnd，ZEnd).

此代码输出:

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

我该如何解决这个问题?

解决方案

当第一个参数的列表长度未知时，@Boris 的回答不会终止.要看到这一点，除了带有 失败切片:

<预>div(L, L1, L2, L3) :-长度(L，Len)，假，% 在这里你计算例如 Len1 和 Len2长度(L1, Len1),长度(L2, Len2),append(L1, L1_suffix, L),追加(L2，L3，L1_suffix).

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

div(A,B,C,D) 终止_if b(A);b(B);b(C);b(D).

换句话说，为了确保终止，您只需要一个参数(A 或 B 或 C 或 D) 成为一个具体的有限列表(这就是 b(..) 的意思).这是一个非常强的终止条件.真可惜，论据不合适！为什么不概括你的程序?它唯一的问题是它限制了列表元素.所以我将用 _s 替换列表元素的所有变量名:

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

非常相同的终止属性适用于此程序.

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

divnew(Zs, As, Bs, Cs) :-gdiv(Zs, As, Bs, Cs),追加(作为，BsCs，Zs)，追加(Bs，Cs，BsCs).

我更喜欢的表达方式是:

divnew(Zs, As, Bs, Cs) :-gdiv(Zs, As, Bs, Cs),短语((seq(As)，seq(Bs)，seq(Cs))，Zs).

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

I am trying to make a function that splits a list of variable length into three lists of even length in order. The following splits it into three, but processes inserts them into each list one at a time.

An example of what I want is:

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

Another example would be:

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

The following code splits them by inserting into each list one at a time:

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).

This code outputs:

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

How can I fix this problem?

解决方案

The answer by @Boris does not terminate when the length of the list of the first argument is not known. To see this, there is no need to look any further than the first goal with a failure-slice:

div(L, L1, L2, L3) :-
    length(L, Len), false,
    % here you compute for example Len1 and Len2
    length(L1, Len1),
    length(L2, Len2),
    append(L1, L1_suffix, L),
    append(L2, L3, L1_suffix).

On the other hand, your original program had quite nice termination properties. cTI gave the following optimal termination property:

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

In other words, to ensure termination, you only need a single argument (either A or B or C or D) to be a concrete list that is finite and ground (that's what b(..) means). That is a very strong termination condition. It's really a pity that the arguments do not fit! Why not generalize your program? The only problem it has is that it restricts the list elements. So I will replace all variable names of list elements by _s:

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

The very same termination properties hold for this program.

Alas, it is now a bit too general. Boris's solution can now be repurposed:

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

My preferred way to express the same would rather be:

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

See other answers for a definition of seq//1.

这篇关于使用 Prolog 按顺序将单个列表拆分为三个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！