如何从序言中的列表中删除每个出现的子列表? [英] How can I delete every occurrence of a sublist from a list in prolog?

问题描述

这是从给定列表中删除或移除元素的代码:

remove_elem(X,[],[]).remove_elem(X,L1,L2) :-L1 = [H|T]，X == H，remove_elem(X,T,Temp),L2 = 温度.remove_elem(X,L1,L2) :-L1 = [H|T]，X == H,remove_elem(X,T,Temp),L2 = [H|温度].

如何修改它，以便从列表中删除每个出现的子列表?

当我试图将一个列表放入一个元素中时，它只会删除该元素并且只删除一次.

应该是这样的:

?- remove([1,2],[1,2,3,4,1,2,5,6,1,2,1],L).L = [3,4,5,6,1].％ 预期结果

解决方案

这个逻辑上纯粹的实现是基于谓词 if_/3 和 (=)/3.

首先，我们构建一个prefix_of/2的具体化版本:

prefix_of_t([],_,true).prefix_of_t([X|Xs],Zs,T) :-prefix_of_t__aux(Zs,X,Xs,T).prefix_of_t__aux([],_,_,false).prefix_of_t__aux([Z|Zs],X,Xs,T) :-if_(X=Z, prefix_of_t(Xs,Zs,T), T=false).

然后，进入主谓词list_sublist_removed/3:

list_sublist_removed([],[_|_],[]).list_sublist_removed([X|Xs],[L|Ls],Zs) :-if_(prefix_of_t([L|Ls],[X|Xs]), % 测试(Zs = Zs0, append([L|Ls],Xs0,[X|Xs])), % case 1(Zs = [X|Zs0], Xs0 = Xs)), % case 2list_sublist_removed(Xs0,[L|Ls],Zs0).

list_sublist_removed/3的递归子句的一些操作说明:

1. 首先(测试)，我们检查[L|Ls]是否是[X|Xs]的前缀.

2. 如果它存在(情况 1)，我们将其从 [X|Xs] 中剥离，产生 Xs0 并且不向 Zs.

3. 如果它不存在(情况 2)，我们从 [X|Xs] 中去除 X 并将 X 添加到 <代码>Zs.

4. 我们递归 [X|Xs] 的其余部分，直到没有更多的项目需要处理.

<小时>

接下来是一些查询！

1. 您在问题中给出的用例:

   <上一页>?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],[1,2],L).L = [3,4,5,6,1].% 确定性地成功

2. 尝试查找已删除子列表的两个查询:

   <上一页>?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[ 3,4,5,6,1]).子 = [1,2] ?;不?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[1,3,4,5,6,1]).不

3. 接下来，让我们在这个查询中找到一个合适的Ls:

   <上一页>?- list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).% 很多时间过去了……什么也没发生！

   不终止！这是不幸的，但在预期之内，因为解决方案集是无限的.但是，通过先验约束 Ls 的长度，我们可以得到所有预期的结果:

   <上一页>?- 长度(Ls,_), list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).Ls = [ 3,4,5,6,1] ?;Ls = [1,2, 3,4,5,6,1] ?;Ls = [3, 1,2, 4,5,6,1] ?;Ls = [3,4, 1,2, 5,6,1] ?;Ls = [3,4,5, 1,2, 6,1] ?;Ls = [3,4,5,6, 1,2, 1] ?;Ls = [3,4,5,6,1, 1,2 ] ?;Ls = [1,2, 1,2, 3,4,5,6,1] ?...

This is the code for deleting or removing an element from a given list:

remove_elem(X,[],[]). 
remove_elem(X,L1,L2) :-
   L1 = [H|T],
   X == H,
   remove_elem(X,T,Temp),
   L2 = Temp. 
remove_elem(X,L1,L2) :- 
   L1 = [H|T],
   X == H, 
   remove_elem(X,T,Temp),
   L2 = [H|Temp].

How can I modify it, so that I can delete every occurrence of a sub list from a list?

When I tried to put a list in an element, it only deletes the element and only once.

It should be this:

?- remove([1,2],[1,2,3,4,1,2,5,6,1,2,1],L).   
L = [3,4,5,6,1].                        % expected result

解决方案

This logically pure implementation is based on the predicates if_/3 and (=)/3.

First, we build a reified version of prefix_of/2:

prefix_of_t([],_,true).
prefix_of_t([X|Xs],Zs,T) :-
   prefix_of_t__aux(Zs,X,Xs,T).

prefix_of_t__aux([],_,_,false).
prefix_of_t__aux([Z|Zs],X,Xs,T) :-
   if_(X=Z, prefix_of_t(Xs,Zs,T), T=false).

Then, on to the main predicate list_sublist_removed/3:

list_sublist_removed([],[_|_],[]).
list_sublist_removed([X|Xs],[L|Ls],Zs) :-
    if_(prefix_of_t([L|Ls],[X|Xs]),                 % test
        (Zs = Zs0,     append([L|Ls],Xs0,[X|Xs])),  % case 1
        (Zs = [X|Zs0], Xs0 = Xs)),                  % case 2
    list_sublist_removed(Xs0,[L|Ls],Zs0).

A few operational notes on the recursive clause of list_sublist_removed/3:

1. First (test), we check if [L|Ls] is a prefix of [X|Xs].

2. If it is present (case 1), we strip it off [X|Xs] yielding Xs0 and add nothing to Zs.

3. If it is absent (case 2), we strip X off [X|Xs] and add X to Zs.

4. We recurse on the rest of [X|Xs] until no more items are left to process.

---

Onwards to some queries!

1. The use case you gave in your question:

   ?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],[1,2],L).
   L = [3,4,5,6,1].                           % succeeds deterministically
   

2. Two queries that try to find the sublist that was removed:

   ?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[  3,4,5,6,1]).
   Sub = [1,2] ? ;
   no
   
   ?- list_sublist_removed([1,2,3,4,1,2,5,6,1,2,1],Sub,[1,3,4,5,6,1]).
   no
   

3. Next, let's find a suitable Ls in this query:

      
   ?- list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).
   % a lot of time passes ... and nothing happens!
   

   Non-termination! This is unfortunate, but within expectations, as the solution set is infinite. However, by a-priori constraining the length of Ls, we can get all expected results:

   ?- length(Ls,_), list_sublist_removed(Ls,[1,2],[3,4,5,6,1]).
     Ls = [      3,4,5,6,1]     ?
   ; Ls = [1,2,  3,4,5,6,1]     ?
   ; Ls = [3, 1,2, 4,5,6,1]     ?
   ; Ls = [3,4, 1,2, 5,6,1]     ?
   ; Ls = [3,4,5, 1,2, 6,1]     ?
   ; Ls = [3,4,5,6, 1,2, 1]     ?
   ; Ls = [3,4,5,6,1, 1,2 ]     ?
   ; Ls = [1,2, 1,2, 3,4,5,6,1] ? ...
   

这篇关于如何从序言中的列表中删除每个出现的子列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！