gprolog-确定一个列表是否为另一个列表的简单方法 [英] gprolog - Simple way to determine whether one list is a permutation of another

问题描述

我正在尝试编写一个序言程序，该程序确定一个列表是否是另一个列表的排列.输入的格式为perm(L,M)，当且仅当列表L是列表M的排列时，该输入才为true.

I'm trying to write a prolog program that determines whether one list is a permutation of another. Input is of the form perm(L,M), which will be true if and only if list L is a permutation of list M.

这是我的AI课，所以我不能只使用gprolog已经提供的漂亮的permutation谓词.我们的教授指出，member谓词可能有用，但是我所涉及的任何想法似乎都需要非常棘手且不太明确的事情(而且我认为有一种方法可以解决此问题而又不会太高级，因为该课程是prolog的新课程.)

This is for my AI class, so I cannot just use the nifty little permutation predicate that gprolog already provides. Our professor noted that the member predicate might be useful, but any ideas I have that involve it seem to require very tricky and not-so-declarative things (and I'm assuming there is a way to solve this without getting too advanced, since the class is new to prolog.)

无论如何，一种检查方法应该是查看L和M的大小相同，每个L元素在M中，每个M元素在L中(有member的用法！).但是，对于[2,2,4]和[4,4,2]等情况，这还不够.

Anyway, one way to check would supposedly be to see that L and M are the same size, each L element is in M, and each M element is in L (there's a use of member!). However, this wouldn't be enough for cases like [2,2,4] and [4,4,2], among others.

另一种方法可能是确保每个元素的相同计数在相反的列表中，但是我对序言的印象是，任何类型的变量内存"都是相当困难的事情(实际上，示例程序似乎我看到执行排序等操作根本就不是在操纵数据；它们只是在假设"地重新安排事情，然后告诉您是或否...?)

Another way could be to ensure that the same counts of each element are in the opposite list, but my impression of prolog is that any kind of variable 'memory' is rather difficult business (in fact, it seems that the example programs I see that perform sorts, etc., aren't really manipulating data at all; they're just 'hypothetically' rearranging things and then telling you yes or no...?)

从精神上讲，人们可以同时对列表和元素进行排序，但是在其他许多思考方式中，它似乎有点面向对象...

Mentally, one could just sort both lists and check elements side-by-side, but that, among tons of other ways to think of it, seems a little too object-oriented...

有任何提示吗?我最大的麻烦似乎是(如上所述)一个事实，即操作"似乎更像是对他们的询问，并希望事情能够持续足够长的时间才能到达您想要的位置.

Any hints? My biggest trouble seems to be (as mentioned) the fact that doing "operations" seems to be more like asking about them and hoping that things stay true long enough to get where you want.

**更新:gprolog确实提供了delete功能，但是伴随这样的尝试，它伴随了我所期望的与声明有关的麻烦:

**UPDATE: gprolog does offer a delete functionality, but it comes with the declarative-related trouble I was expecting, given an attempt like this:

perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).

在手册中，删除的定义如下:"delete(List1，Element，List2)删除List1中所有出现的Element以提供List2.需要严格的术语相等，请参阅(==)/2"

In the manual, delete is defined like this: "delete(List1, Element, List2) removes all occurrences of Element in List1 to provide List2. A strict term equality is required, cf. (==)/2"

执行:

{trace}
| ?- perm([1,2,3],[3,1,2]).
      1    1  Call: perm([1,2,3],[3,1,2]) ? 
      2    2  Call: member(1,[3,1,2]) ? 
      2    2  Exit: member(1,[3,1,2]) ? 
      3    2  Call: delete([1,2,3],1,[3,1,2]) ? 
      3    2  Fail: delete([1,2,3],1,[3,1,2]) ? 
      2    2  Redo: member(1,[3,1,2]) ? 
      2    2  Fail: member(1,[3,1,2]) ? 
      1    1  Fail: perm([1,2,3],[3,1,2]) ? 

(1 ms) no

**更新2:我想我可能已经知道了！这有点冗长，但是我已经在很多情况下对其进行了测试，但还没有发现不好的情况.如果有人发现重大问题，请指出:

**UPDATE 2: I think I might have figured it out! It's kind of verbose, but I have tested it for quite a few cases and haven't found a bad one yet. If someone sees a major issue, please point it out:

perm([],[]). 
perm([LH|LT],R) :- length([LH|LT],A), length(R,B), A == B, member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.
perm_recurse([],X).  %If we get here, all elements successfully matched
perm_recurse([LH|LT],R) :- member(LH,R), select(LH,[LH|LT],X), select(LH,R,Y), perm_recurse(X, Y), !.  

我喜欢剪切运算符.

推荐答案

总是可以定义更笼统的谓词并以狭窄的方式使用它:

Always good to define more general predicate and use it in a narrowed fashion:

perm(X,L):- mselect(X,L,[]).

mselect([A|B],L,R):- select(A,L,M), mselect(B,M,R).
mselect([],L,L).

member不好，因为它使第二个列表保持不变. delete也不好，因为它删除了多重性.

member is no good as it leaves the second list unchanged. delete is no good either as it deletes the multiplicities.

您可以使用append. :)它也结合了选择和删除:

You could use append though. :) It too combines picking and removing:

perm([A|B],L):- length(L,N), between(0,N,I),length(X,I),
  append(X,[A],Y), append(Y,Z,L),
  append(X,Z,M), perm(B,M).
perm([],[]).

这篇关于gprolog-确定一个列表是否为另一个列表的简单方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！