logo标签列表

在Prolog中合并两个列表

prolog
4
你如何将两个列表合并？这是我尝试过的方法，但它没有给我想要的结果。
Y = [1,2,3].
Z = [3,4,5].
X = [Y,Z].

这只是一个更大的列表，分为头部和尾部。

我希望我的输出看起来像这样:

X = [1,2,3,4,5].
只是为了明确，3 在两个列表中都出现了，但你只想在输出中出现一次？ - Enigmativity
您似乎接受了一个保留重复项的答案。您能确认所需的行为吗？ - Enigmativity
1
赏金文本应该是：对于@gusbro在/a/66450073中最初定义的纯版本。理想情况下，还应列举所有length(Zs，_），combine（Xs，Ys，Zs）的答案。对于combine([a|_],_,[b|_]).等情况会失败。 - false
1
@false，你是否认为(@<)/2在你的奖励目的中是纯粹的？ - Isabelle Newbie
1
@IsabelleNewbie：a @< X 失败了。但是，X = b, a @< X 成功了。你需要将它隐藏在一些干净的接口背后。 - false
显示剩余3条评论
7个回答
4
如果你想将两个可能重叠的地面列表合并为第三个列表，并且在结果中仅保留重叠元素的一个副本（即第一个列表的后缀元素也是第二个列表的前缀元素），可以按照以下方式编写代码：
combine(A, B, C):-
  append(A1, Common, A),
  append(Common, B1, B),
  !,  % The cut here is to keep the longest common sub-list
  append([A1, Common, B1], C).

示例运行:

?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5].

?- combine([1,2,3,4],[3,4,5], C).
C = [1, 2, 3, 4, 5].

稍作修改以避免使用cut：

combine(A, B, C):-
  append(A1, Common, A),
  append(Common, B1, B),
  bagof(NotCommonA-NotCommonB,
        not_common(A1, B1, NotCommonA, NotCommonB),
        LDifs),
  maplist(difpair, LDifs),
  append([A1, Common, B1], C).
  
not_common(L, R, [ItemA|NotCommonA], NotCommonB):-
  append(_, [ItemA|NotCommonA], L),
  length([ItemA|NotCommonA], LNotCommon),
  length(NotCommonB, LNotCommon),
  append(NotCommonB, _, R).

difpair(L-R):-
  dif(L, R).

示例运行：

?- combine([1,2,3],[3,4,5], C).
C = [1, 2, 3, 4, 5] ;
false.

?- combine([1,2,3,X],[3,4,5], C).
X = 4,
C = [1, 2, 3, 4, 5] ;
X = 3,
C = [1, 2, 3, 3, 4, 5] ;
C = [1, 2, 3, X, 3, 4, 5],
dif(X, 3),
dif(X, 4) ;
;
false
我已经进行了编辑和还原，以演示一些东西。请问您的意见，这种编码风格对新手学习有帮助吗？ - Will Ness
1
@Will：除了缩进之外，有没有一种清晰的方法来删除这个剪切呢？ - false
@false：编辑后的答案中的方法怎么样？我想使用foreach/2，但至少在我的SWI中它会创建未绑定变量的副本，所以最终我使用了bagof+maplist。 - gusbro
@false 嗯，有趣的挑战。目前我没有看到一个干净（位置/结构）的方法来做到这一点。 :) - Will Ness
2
明显可以获得赏金！ - false
3
这个问题完全不清楚：是关于合并已排序的列表吗？也许是数字的已排序列表？是否是一种仅保留第一个列表共享后缀/第二个列表前缀的附加操作？还是某种更一般意义上的去重？
下面是一个解决方案，它会删除共享的后缀/前缀。这与Slago的解决方案类似，但它使用两个谓词来表示计算可能处于的两种不同状态：merge 从第一个参数“复制”元素到第三个参数；在某个时刻，它切换到 mergerest，该函数“保持复制”，但需要其第一个参数是第二个参数的非空前缀。
merge(Xs, Ys, Zs) :-
    mergerest(Xs, Ys, Zs).
merge([X|Xs], [Y|Ys], [X|Zs]) :-
    merge(Xs, [Y|Ys], Zs).

mergerest([X], [X|Ys], [X|Ys]).
mergerest([X|Xs], [X|Ys], [X|Zs]) :-
    mergerest(Xs, Ys, Zs).

使用false的动物定义:

?- animal(A), animal(B), dif(A, Mutation), merge(A, B, Mutation).
A = [a,l,l,i,g,a,t,o,r],
B = [t,o,r,t,u,e],
Mutation = [a,l,l,i,g,a,t,o,r,t,u,e] ;
A = [c,a,r,i,b,o,u],
B = [o,u,r,s],
Mutation = [c,a,r,i,b,o,u,r,s] ;
A = [c,h,e,v,a,l],
B = [a,l,l,i,g,a,t,o,r],
Mutation = [c,h,e,v,a,l,l,i,g,a,t,o,r] ;
A = [c,h,e,v,a,l],
B = [l,a,p,i,n],
Mutation = [c,h,e,v,a,l,a,p,i,n] ;
A = [v,a,c,h,e],
B = [c,h,e,v,a,l],
Mutation = [v,a,c,h,e,v,a,l] ;
false.

仅当第三个参数绑定时的行为，例如：

?- merge(Xs, Ys, [1, 2, 3]).
Xs = [1],
Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [1, 2, 3] ;
Xs = Ys, Ys = [1, 2, 3] ;
Xs = [1, 2],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [2, 3] ;
Xs = [1, 2, 3],
Ys = [3] ;
false.

更普遍地说：

?- length(Zs,_), merge(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [_4262] ;
Zs = Ys, Ys = [_4262, _4268],
Xs = [_4262] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268] ;
Zs = Xs, Xs = [_4262, _4268],
Ys = [_4268] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274],
Xs = [_4262, _4268] ;
Zs = Xs, Xs = Ys, Ys = [_4262, _4268, _4274] ;
Zs = [_4262, _4268, _4274],
Xs = [_4262, _4268],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4268, _4274] ;
Zs = Xs, Xs = [_4262, _4268, _4274],
Ys = [_4274] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262] ;
Zs = Ys, Ys = [_4262, _4268, _4274, _4280],
Xs = [_4262, _4268] .  % ad nauseam

快速失败：

?- merge([a|_],_,[b|_]).
false.
merge("iguana","anaconda",L). 有两种解决方案，而不是一种。 - false
@false 这是真的。太遗憾了，没有规范告诉我们需要什么。 - Isabelle Newbie
看一下被接受的答案。显然那就是规范！ - false
2
这里是一个测试程序（自从Meloni，1976年以来），为了避免转换和琐碎的解决方案而简化。请参见iwhen/2的定义，并将字符作为双引号字符串在答案替换中打印出来。
:- set_prolog_flag(double_quotes, chars).

animal("alligator").
animal("tortue").
animal("caribou").
animal("ours").
animal("cheval").
animal("vache").
animal("lapin").
% animal("iguana").
% animal("anaconda").

mutation(C) :-
   animal(A),
   animal(B),
   dif(A, C),
   combine(A, B, C),
   iwhen(ground(A+B+C), \+ append(A, B, C) ).

?- mutation(C).
   C = "alligatortue"
;  C = "caribours"
;  C = "chevalligator"
;  C = "chevalapin"
;  C = "vacheval"
;  false.
2
这是对该问题的另一种看法：
combine([A|As], [B|Bs], [A|Cs]):-
  dif(A, B),
  combine(As, [B|Bs], Cs).
combine(As, Bs, Cs):-
  suffix_prefix(As, Bs, Cs).
combine([A|As], [A|Bs], [A|Cs]):-
  not_suffix_prefix(As, Bs, Cs),
  combine(As, [A|Bs], Cs).
  
suffix_prefix([], Bs, Bs).
suffix_prefix([A|As], [A|Bs], [A|Cs]):-
  suffix_prefix(As, Bs, Cs).

not_suffix_prefix([_|_], [], [_|_]).
not_suffix_prefix([A|As], [A|Bs], [_|Cs]):-
  not_suffix_prefix(As, Bs, Cs).
not_suffix_prefix([A|_], [B|_], _):-
  dif(A, B).

以下是样例运行结果(来自测试答案)，对于combine([a|_], _, [b|_])的失败，生成所有的解决方案以及其他一些测试：

?- mutation(C).
C = [a, l, l, i, g, a, t, o, r, t, u, e] ;
C = [c, a, r, i, b, o, u, r, s] ;
C = [c, h, e, v, a, l, l, i, g, a, t, o, r] ;
C = [c, h, e, v, a, l, a, p, i, n] ;
C = [v, a, c, h, e, v, a, l] ;
false.

?- combine([a|_], _, [b|_]).
false.

?- combine([1,2,3], [3,4,5], Cs).
Cs = [1, 2, 3, 4, 5] ;
false.

?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1, 2, 3, 4, 5] ;
Cs = [1, 2, 3, '$VAR'('X'), 3, 4, 5],
dif('$VAR'('X'), 3),
dif('$VAR'('X'), 4) ;
;
X = 3,
Cs = [1, 2, 3, 3, 4, 5] ;
false.

?- combine([A,A], [A], C).
C = ['$VAR'('A'), '$VAR'('A')] ;
false.

?- length(Zs, Len), combine(Xs, Ys, Zs).
Zs = Xs, Xs = Ys, Ys = [],
Len = 0 ;
Zs = Ys, Ys = [_2419916],
Len = 1,
Xs = [] ;
Zs = Xs, Xs = Ys, Ys = [_2419916],
Len = 1 ;
Zs = [_2420492, _2420498],
Len = 2,
Xs = [_2420492],
Ys = [_2420498],
dif(_2420492, _2420498) ;
;
Zs = Xs, Xs = [_2420498, _2420504],
Len = 2,
Ys = [_2420504],
dif(_2420498, _2420504) ;
;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [] ;
Zs = Ys, Ys = [_2419916, _2419922],
Len = 2,
Xs = [_2419916] ;
Zs = Xs, Xs = Ys, Ys = [_2419916, _2419922],
Len = 2 ;
Zs = Xs, Xs = [_2419916, _2419916],
Len = 2,
Ys = [_2419916] ;
Zs = [_2420690, _2420696, _2420702],
Len = 3,
Xs = [_2420690, _2420696],
Ys = [_2420702],
dif(_2420690, _2420702),
dif(_2420696, _2420702) ;

.... continues ...
@WillNess：运行该示例时，我发现combine/3的基本情况存在问题（缺少一些解决方案）。已经修复并重新运行了所有示例，包括第一个答案中的我的示例运行。 - gusbro
正如我在答案中所指出的，我认为这个调用应该成功：combine2([A,A],[A],C)，但根据你的谓词却没有成功（除非我误解了定义）。 - jnmonette
这个'$VAR'('X')是从哪里来的？ - false
@false: 如果你指的是 combine([1,2,3,X],[3,4,5], Cs) 的结果，我相信这是使用 SWI 中的 dif/2 导致的。我不记得看到过这样的答案，但当我使用 dif/2 时，它们出现在我的 SWI 8.0.2 版本中，而且我认为 '$VAR'('X') 只是表示 X。 - gusbro
最新添加创建了另一个非常小的问题：对于 length(Zs, Len), combine(Xs, Ys, Zs). 的两个解法是 combine([A,A],[A],[A,A]) 和 combine([A,B],[B],[A,B]), dif(A,B)。在我的方法中，我设法消除了这种冗余，并只有一个单独的 combine([A,B],[B],[A,B])（没有 dif 条件），这需要引入 longer/2 和 not_longer/2。 - jnmonette
显示剩余4条评论
2

这里有另一种解决方案，与gusbro的相似但修复了一些缺失的情况（例如combine([A,A],[A],C)应该成功，结果为C=[A,A]）。

% Third is the concatenation of First and Second but without the longest suffix
combine(As,Bs,Bs):-         %     of First that is also a prefix of Second
    prefix(As,Bs).
combine([A|As],Bs,[A|Cs]):-
    prefix(As, Cs),         % Necessary when As is var to avoid
    not_prefix([A|As], Bs), %          generating too long lists
    combine(As,Bs,Cs).

% First is prefix of Second
prefix([],_).
prefix([A|As],[A|Bs]):-
    prefix(As,Bs).

% First is not prefix of Second
not_prefix(As,Bs):-
    longer(As,Bs).
not_prefix(As,Bs):-
    not_longer(As,Bs),
    not_prefix2(As,Bs).

% First is not prefix of Second, knowing it is not longer
not_prefix2([A|As],[A|Bs]):-
    not_prefix2(As,Bs).
not_prefix2([A|_],[B|_]):-
    dif(A,B).

% First is longer than Second
longer([_|_], []).
longer([_|As],[_|Bs]):-
    longer(As,Bs).

% First is not longer than Second
not_longer([], _).
not_longer([_|As],[_|Bs]):-
    not_longer(As,Bs).

一些测试：

?- combine([1,2,3], [3,4,5], Cs).
Cs = [1,2,3,4,5] ? ;
no

?- combine([1,2,3,X], [3,4,5], Cs).
X = 4,
Cs = [1,2,3,4,5] ? ;
X = 3,
Cs = [1,2,3,3,4,5] ? ;
Cs = [1,2,3,X,3,4,5],
prolog:dif(X,4),
prolog:dif(X,3) ? ;
no

?- combine([a|_], _, [b|_]).
no

?- length(Cs, Len), combine(As, Bs, Cs).
Cs = [],
Len = 0,
As = [],
Bs = [] ? ;
Cs = [_A],
Len = 1,
As = [],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [_A] ? ;
Cs = [_A],
Len = 1,
As = [_A],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_A,_B] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A],
Bs = [_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [] ? ;
Cs = [_A,_B],
Len = 2,
As = [_A,_B],
Bs = [_B] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_A,_B,_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_C],
prolog:dif(_B,_C) ? ;
Cs = [_A,_A,_B],
Len = 3,
As = [_A,_A],
Bs = [_A,_B],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B],
Bs = [_B,_C],
prolog:dif(_A,_B) ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_C] ? ;
Cs = [_A,_B,_C],
Len = 3,
As = [_A,_B,_C],
Bs = [_B,_C] ? ;
Cs = [_A,_B,_C,_D],
Len = 4,
As = [],
Bs = [_A,_B,_C,_D] ? 
yes
1

我不认为你的做法是 Prolog 的工作方式（你所做的并不是你想象中的赋值操作）。

但无论如何，以下是如何将两个列表连接起来的方法：

?- append([1,2,3],[3,4,5],X).
returns: X = [1, 2, 3, 3, 4, 5].
如下所示，正如gusbro在下面指出的那样，您可能还对两个列表的并集感兴趣: union([1,2,3],[3,4,5],X). 返回 X=[1,2,3,4,5]。 - Tasos Papastylianou
但是 union( [1,2,3], [5,3,4,5], X) 应该得到 X = [1, 2, 5, 3, 4, 5] 而不是 X = [1, 2, 3, 5, 3, 4, 5]。 - Will Ness
1
@WillNess确实，但是目前这只与问题有关，因为现在问题已经被重新解释了大约3次。对于一个有效地展示提问者仍在努力理解统一和赋值之间有效区别的问题 :p - Tasos Papastylianou
1
一种可能的解决方案是：

：

combine([], B, B).
combine(A, [], A).
combine([X|A], [X|B], [X|C]) :- combine(A, B, C).
combine([X|A], [Y|B], [X|C]) :- dif(X,Y), combine(A, [Y|B], C).

一些查询：
?- combine([1,2,3,4,5], [3,4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.

?- combine([1,2,3,4,5], [4,5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.

?- combine([1,2,3,4,5], [5,6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.

?- combine([1,2,3,4,5], [6,7], C).
C = [1, 2, 3, 4, 5, 6, 7] ;
false.

?- combine([1,2,3,4,5], [], C).
C = [1, 2, 3, 4, 5] ;
false.

?- combine([], [3,4,5,6,7], C).
C = [3, 4, 5, 6, 7] ;
false.
combine("vacheval","vel","vacheval") 的成功结果不正确。 - false
在问题的评论中，提问者说：“我想将(...)附加到一个谓词上，以删除其中一个重复项”。因此，我认为答案对于提问者提出的问题是正确的。 - slago
至少对于赏金，其含义由gusbro的第一个定义给出。而且，“删除重复项之一”显然也不是一个明确的要求，我想知道在上述情况下实际上删除了什么。 - false
@false 我回答问题时并没有打算获得赏金。至于被删除的内容，很容易看出 [v, a, c, h, e, v, a, l] 包含了 [v, e, l]，那么被删除的项就是 v, e 和 l。 - slago
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接