使用元素插入的Prolog置换谓词 [英] Prolog permutation predicate using insertion of elements

问题描述

我正在尝试编写谓词permutation/2，以便仅当两个参数都为list时，才为true，一个是另一个的置换.为此，我编写了两个辅助谓词delete/3和insert/3.当且仅当第三个参数是第二个参数(两个列表都删除了第一个参数中的元素的第一个实例)时，第一个才为true.当且仅当第三个参数等于插入了第一个参数(元素)的第二个参数时，第二个才是真.

I am trying to write a predicate permutation/2 so that it is true if and only if both arguments are list, one a permutation of the other. To do this, I've written the two helper predicates delete/3 and insert/3. The first is true if and only if the third argument is the second argument, both lists, with the first instance of the element in the first argument removed. The second is true if and only if the third argument equals the second argument with the first argument (element) inserted.

delete(X,[X|T],T). % Base case, element equals head.
delete(X,[A|B],[A|C]) :- delete(X,B,C). % Else, repeat for the tail.

insert(X,[],[X]). % Base case.
insert(X,[H|T],B) :- delete(H,B,U), insert(X,T,U). % Delete all elements from B.

permutation([],[]). % Base case.
permutation([H|T],P) :- permutation(Q,T), insert(H,Q,P). % P a permutation of T, H inserted.

我的想法是查询

?- insert(A,B,X). 

对于给定的A，B应该返回所有实例化X的方式，以使其等于在元素B处添加了元素A的列表B.但是，它不会这样做:

For given A, B should return all ways of instantiating X so that it equals the list B with the element A added somewhere. However, it does not do this:

?- insert(3,[1,2],X).
X = [1, 2, 3] ;
X = [1, 3, 2] ;
ERROR: Out of global stack

我认为这是因为我定义谓词的方式，即检查第三个参数中的列表减去第二个参数中列表的每个元素是否等于仅包含第一个参数的列表，而不是进行构造性定义，但是我很难用另一种方式解决这个问题.然后，排列谓词应通过检查P是否是第一个列表的尾部和随机插入的头部的排列，来递归地检查其第二个参数中的列表是否是排列.感谢帮助！

I think this is because of the way I defined the predicate, checking if the list in the third argument minus every element of the list in the second argument equals the list containing only the first argument, rather than defining it constructively, but I am having a hard time solving this problem another way. The permutation predicate should then check if the list in its second argument is a permutation recursively, by checking if P is a permutation of the tail of the first list with the head randomly inserted. Help is appreciated!

推荐答案

insert/3和delete/3都是相同的谓词，在教科书中与select/3相同.它也在标准库中，例如在SWI-Prolog中，您可以将其找到为select/3.您可以将其用于插入或删除，只需根据需要更改列表的位置即可.

Both insert/3 and delete/3 is the same predicate and it is found in textbooks as select/3. It is also in standard library, for example in SWI-Prolog you can find it as select/3. You can use it to insert or delete, just change the position of the list as necessary.

从"abc"中删除"b":

Delete "b" from "abc":

?- select(b, [a,b,c], X).
X = [a, c] ;
false.

在"ac"中的任何位置插入"b":

Insert "b" in "ac" in any position:

?- select(b, X, [a,c]).
X = [b, a, c] ;
X = [a, b, c] ;
X = [a, c, b] ;
false.

它的定义与您定义delete/3时完全相同，如果您在开源的SWI-Prolog中看到list.pl的源代码，就会看到它.

It is defined exactly as you did define delete/3, if you see the source of lists.pl in SWI-Prolog which is open source you will see it.

select(X, [X|Tail], Tail).
select(Elem, [Head|Tail], [Head|Rest]) :-
    select(Elem, Tail, Rest).

但是现在您可以像描述的那样定义排列.因为我在同一源文件列表中也找到了此文件，所以我只是在此处复制源文件，这是可以的，因为它是开放源代码:

But now you can define permutation just like you described. Because I find also this in the same source file lists.pl I just copy the source here, and it is ok because it is open source:

perm([], []).
perm(List, [First|Perm]) :-
    select(First, List, Rest),
    perm(Rest, Perm).

我使用lists:perm是因为它是私有"的，但它不是私有的，只是不导出:

I use lists:perm because it is "private" but it is not private it is just not exported:

?- lists:perm([a,b,c], P).
P = [a, b, c] ;
P = [a, c, b] ;
P = [b, a, c] ;
P = [b, c, a] ;
P = [c, a, b] ;
P = [c, b, a] ;
false.

?- lists:perm([a,b,c], [b,a,c]).
true ;
false.

我只有一条信息，那就是:阅读教科书并阅读源代码，因为它可以帮助您更快地学习.

I have just one message and it is: read the textbook and read the source because it helps you learn much faster.

这篇关于使用元素插入的Prolog置换谓词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！