如何在Prolog中删除子列表？

Question

请问有人能帮我吗？我需要用Prolog解决这个问题，但我不知道该如何处理...

"给定一个整数列表。删除由下降元素组成的所有子列表。"

- user3671805

---

你能展示一些尝试吗？请阅读关于如何提出正确问题的Stackoverflow Tour。 - lurker

Answer 1

我们通过三个步骤来移除降序子列表：

1. separate decreasing and non-decreasing parts (using splitlistIfAdj/3 and (#=<)/3)

   ?- splitlistIfAdj(#=<,[ 1 , 2 , 3 , 4,3,2,1 , 2 , 3 , 4,3,2,1 , 2 ],Xs1).
   Xs1 =                 [[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]].
   

2. exclude non-singleton lists (using tfilter/3, Prolog lambdas, and (=)/3)

   ?- tfilter(\[_|T]^(T=[]),[[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]],Xs2).
   Xs2 =                    [[1],[2],[3],          [2],[3],          [2]].
   

3. map singleton lists to items (using maplist/3 and Prolog lambdas)

   ?- maplist(\[H|_]^H^true,[[1],[2],[3],[2],[3],[2]],Xs).
   Xs =                     [ 1 , 2 , 3 , 2 , 3 , 2 ].
   

让我们把它放在一起！

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

descending_removed(Xs0,Xs) :-
   splitlistIfAdj(#=<,Xs0,Xs1),
   tfilter(\[_|T]^(T=[]),Xs1,Xs2),
   maplist(\[H|_]^H^true,Xs2,Xs).

以下是一些查询：

?- descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],Xs).
Xs = [1,2,3,2,3,2].

?- descending_removed([4,3,2,1,0],Xs).
Xs = [].

?- descending_removed([1,2,3,4],Xs).
Xs = [1,2,3,4].

?- descending_removed([1,2,3,  4,3,3,2,2,1],Xs).
Xs = [1,2,3].

?- descending_removed([1,2,3,4,4,3,3,2,2,1],Xs).
Xs = [1,2,3,4].

- repeat

Answer 2

我们可以通过使用tchoose/3而不是tfilter/3和maplist/3，在两个步骤中移除降序子列表，来改进这个答案：

1. separate decreasing and non-decreasing parts (using splitlistIfAdj/3 and (#=<)/3)

   ?- splitlistIfAdj(#=<,[ 1 , 2 , 3 , 4,3,2,1 , 2 , 3 , 4,3,2,1 , 2 ],Xs1).
   Xs1 =                 [[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]].
   

2. filter singleton lists and map to items (using tchoose/3, Prolog lambdas, and (=)/3)

   ?- tchoose(\[H|T]^H^(T=[]),[[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]],Xs).
   Xs =                       [ 1 , 2 , 3 ,           2 , 3 ,           2 ].
   

让我们将它们组合在一起！

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

descending_removed(Xs0,Xs) :-
   splitlistIfAdj(#=<,Xs0,Xs1),
   tchoose(\[H|T]^H^(T=[]),Xs1,Xs).

相同的查询，相同的结果：

?- descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],Xs).
Xs = [1,2,3,2,3,2].

?- descending_removed([4,3,2,1,0],Xs).
Xs = [].

?- descending_removed([1,2,3,4],Xs).
Xs = [1,2,3,4].

?- descending_removed([1,2,3,  4,3,3,2,2,1],Xs).
Xs = [1,2,3].

?- descending_removed([1,2,3,4,4,3,3,2,2,1],Xs).
Xs = [1,2,3,4].

- repeat

---

查询“descending_removed([1,2,3,3,2,4,3,3,2,2,5],R)”会提供什么结果？（抱歉，没有lambda包可以自行测试）。 - pasaba por aqui

@pasabaporaqui：你使用的是哪个Prolog系统？你应该能够将无模块版本复制粘贴到任何符合规范的系统中。 - false

Answer 3

让我们从一些数字列表的样例开始：

1 2 3 4 3 2 1 2 3 4 3 2 1 2

消除所有递减子列表后，我们应该有：

1 2 3 2 3 2

这怎么做呢？我建议逐个观察列表，并在查看数字组时观察“输出”是如何生成的：

A B C
  1 2   -> output 1
1 2 3   -> output 2
2 3 4   -> output 3
3 4 3   -> output none
4 3 2   -> output none
3 2 1   -> output none
2 1 2   -> output none
1 2 3   -> output 2
2 3 4   -> output 3
3 4 3   -> output none
4 3 2   -> output none
3 2 1   -> output none
2 1 2   -> output none
1 2     -> output 2

我们可以看到，只有当A < B < C时，我们才从中间列B输出数字。因此，我们可以这样做：遍历整个列表并检查数字三元组。如果它们被排序了，那么我们就输出B。

remove_dec([], []).
remove_dec(Input, Output) :-
    min_list(Input, Min),
    remove_dec0([ Min | Input ], Output).
remove_dec0([ A, B, C | Input], [ B | Output ]) :-
    A =< B, B =< C,
    remove_dec0([ B, C | Input], Output).
remove_dec0([ _, B, C | Input], Output) :-
    remove_dec0([ B, C | Input], Output).
remove_dec0([A, B], [B]) :-
    A =< B.
remove_dec0([A, B], []) :-
    A > B.

样例输入和输出：

?- remove_dec([1,2,3,4,3,2,1,2,3,4,3,2,1,2],R).
R = [1, 2, 3, 2, 3, 2] .

?- remove_dec([4,3,2,1,0],R).
R = [] ;
false.

?- remove_dec([1,2,3,4],R).
R = [1, 2, 3, 4] .

- Grzegorz Adam Kowalski

---

@repeat，你引用的子句不存在。你是在建议用once(A > B;B > C)替换A =< B, B =< C吗？我已经检查过了，结果会出现错误。 - Grzegorz Adam Kowalski

我的意思是子句 remove_dec0([ _, B, C | Input], Output) :- remove_dec0([ B, C | Input], Output). 最好改成：remove_dec0([A,B,C|Input],Output) :- once(A > B;B > C), remove_dec0([B,C|Input],Output). 这样这个子句和它上面的子句就可以互相排斥了（在该层级上不使用剪枝）。 - repeat

@Grzegorz：在 A =< B，B =< C 之后进行截取。 - pasaba por aqui

Answer 4

关于（使用与之前回答中相同的名称和测试）：

descending_removed(L,R) :- dr(a,L,R).

dr(_,[],[]).

dr(DIR,[A|Q],R) :-
  ( [B|_]=Q, A>B ->  
        dr(d,Q,R)
  ;
        dr(a,Q,T), ( DIR=a -> R=[A|T]; R=T )
  ).

验证：

test :-
  descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],[1,2,3,2,3,2]),
  descending_removed([4,3,2,1,0],[]),
  descending_removed([1,2,3,4],[1,2,3,4]),
  descending_removed([1,2,3,4,3,3,2,2,1],[1,2,3]),
  descending_removed([1,2,3,4,4,3,3,2,2,1],[1,2,3,4]),
  descending_removed([1],[1]).

给出以下结果：

[debug]  ?- test.
true ;
false.

如果我们想覆盖两个连续相等值的情况，并且解释它们不改变曲线趋势，我们可以定义如下：

descending_removed(L,R) :- dr(a,L,R).

dr(_,[],[]).

dr(DIR,[A|Q],R) :-
  ( [B|_]=Q, A>B ->  
        dr(d,Q,R)
  ; [B|_]=Q, A=B ->  
        dr(DIR,Q,T), ( DIR=a -> R=[A|T]; R=T )   
  ;   
        dr(a,Q,T), ( DIR=a -> R=[A|T]; R=T )
  ).

生成以下答案：

descending_removed([1,2,2,2,3,4,3,3,2,2,1],R).
R = [1, 2, 2, 2, 3] ;
false

descending_removed([1,2,3,3,2,4,3,3,2,2,5],R).
R = [1, 2, 3, 5]
false

- pasaba por aqui