logo标签列表

在Prolog中将一个列表分成两个长度相等的列表

prolog
3

我正在Prolog中编写谓词，将列表分成两个长度相等的列表。例如：

div([1,2,3,4] , X , Y).
X = [1,2].
Y = [3,4].

这是我的代码，但它不能正常工作：

div(L , L1 , L):- length(L) == length(L1).
div([ H | T ] , [ H | T1] , L2):- div(T , T1 , L2).
一旦您解决了@larsmans指出的length/2问题，您的解决方案仍然似乎尝试构建前半部分列表，但它没有任何代码来处理后半部分。您可能需要一个辅助谓词来处理长度计数器。或者，您可以考虑使用append/3。对于div(L, X, Y)，请查看append(X, Y, L)并约束X或Y的长度。 - lurker
6个回答
7

可能只是：

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).

将列表A和列表B连接起来得到原始列表L，其中列表A的长度为N，列表B的长度也是N。
如果OP在使用SWI Prolog（他们没有说明），那么same_length/2不是ISO谓词。 - lurker
2
也许可以通过预先确定 A 和 B 的长度来减少 append 的迭代次数：div(L, A, B) :- length(L, N), Half is N div 2, length(A, Half), length(B, Half), append(A, B, L)。 - lurker
1
或者说是 O(N^2) 和 O(N)。 - Sergii Dymchenko
2
有一个包含 10,000 个元素的列表，Sergey 的代码：30,006 推理 0.140 CPU，lurker 的代码 5,015 推理 0.000 CPU！ - joel76
1
@SergeyDymchenko 我喜欢你的解决方案（+1），它确实比我的建议更具关联性和优雅性。我认为“更有效”的版本唯一失败的关系情况是当 L 未绑定但其中一个 A 或 B 已绑定时。它会给出正确的解决方案，但在回溯寻找更多解决方案时会一直旋转。它可能可以修改以避免这种情况。然后就只是优雅与高效之间的权衡。当然，代码并不总是关于效率的。 :) - lurker
显示剩余4条评论
5
有趣的是，这个分割并没有使用长度：
div(L, A, B) :-
    split(L, L, A, B).

split(B, [], [], B).

split([H|T], [_, _|T1], [H | T2], B) :-
    split(T, T1, T2, B).

对于一个包含100,000个元素的列表，它使用了50,001个推理，但只用了0.016个CPU。而对于同样的列表，lurker 的代码使用了50,015个推理和0.000个CPU。
1
糟糕！你比我多推理了14步！我有一种预感这个问题有更优雅的解决方案。非常好（+1）。 :) - lurker
你的更快，哪个更有用？ - joel76
1
所以 split/4 使用列表本身作为双重递减的“计数器”，以避免使用 length/2。 - lurker
“最有用”很难判断，这取决于应用程序。在这种情况下，我们可能是在纠结琐事。编码通常是简单性（增强清晰度和可维护性）和效率之间的平衡。我认为你的解决方案达到了良好的平衡。 - lurker
2
length(L) == length(L1)

这不是在Prolog中比较列表长度的方法。它比较''项''length（L）和length（L1）而没有进行解释，即没有调用任何谓词。要比较长度，请执行以下操作：

length(L, N), length(L1, N)

如果你修复了那个问题，你的程序应该更接近正常工作了。
我编辑了它，但仍然不起作用： div(L, L1, L)：- length（L，Q），length（L1，W），Q =：= W。 div（[H | T]，[H | T1]，L2）：- div（T，T1，L2）。 - user3100088
@user3100088 他说你的程序已经“接近”实现了。你能从那里找到答案吗？此外，你不需要使用length(L,Q), length(L1,W), Q =:= W.这种写法，像larsmans所示，只需使用length(L,N), length(L1,N)就足够了。 - lurker
2

我喜欢Sergey的解决方案，因为它既优雅又简单（+1）。这里有另一种方法，它在一些进一步的效率方面不太优雅，因为它修剪了查询append的情况。如果A或B中任意一个是ground，则让它们的长度驱动过程。否则，我们让L的长度驱动它：

div(L, A, B) :-
    (   \+ground(A),
        \+ground(B)
    ->  length(L, N),
        HalfN is N div 2
    ;   true
    ),
    length(A, HalfN),
    length(B, HalfN),
    append(A, B, L).

这将会产生，例如：

| ?-  div2(L, A, B).

A = []
B = []
L = [] ? ;

A = [C]
B = [D]
L = [C,D] ? ;

A = [C,D]
B = [E,F]
L = [C,D,E,F] ?
...

| ?- div([1,2,3|T], A, B).

A = [1,2]
B = [3,C]
T = [C] ? ;

A = [1,2,3]
B = [C,D,E]
T = [C,D,E] ? ;
...

| ?- div(L, [1,2], B).

B = [A,C]
L = [1,2,A,C]

yes
| ?- div([1,2|T], [1,2], [3,4]).

T = [3,4]

yes
| ?-

等等。

0
div(L, A, B) :-
append(A, B, L),
length(A, O),
length(B, N),
((O-1)=:=N;(O+1)=:=N;O=:=N),
!.

就是这样，可以处理奇数长度的字符串 :)

0

这只是一个简单的,

div(L,L1,L2) :- length(L,Len), N is Len/2, split(L,L1,L2,N).
split([H|T],[H|L1],L2,N):- N1 is N-1, split(T,L1,L2,N1).
split(T,[],T,0).
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接