2

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.

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.)

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.

**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).

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"

Execution:

{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

**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), !.

I do like the cut operator..

4

4 回答 4

2

定义更一般的谓词并以狭窄的方式使用它总是好的：

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

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

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

你可以用append。:) 它也结合了拾取和移除：

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([],[]).
于 2013-07-04T19:16:30.617 回答
2 
perm(L, M) :- sort(L, X), sort(M, X).

这让您非常接近并且是完全声明性的（“如果两个列表具有相同的排序表示，则它们是彼此的排列”，但在 Prolog 中排序会删除重复项）。perm([1,2], [2,2,2,1])但是，对于我不确定您是否想要的情况，它将成功。不过，它将处理 [2,2,4] 和 [4,4,2]，因为它们都排序为[2,4]. 另一种解决方案是这样的：

perm([], []).
perm([L|Ls], M) :- select(L, M, Ms), !, perm(Ls, Ms).

此版本对于 [2,2,4] 和 [4,4,2] 不会成功，但对于 [1,2] 和 [2,2,2,1] 会正常失败。我不确定你想要哪一个，但我认为其中一个或另一个可能是正确的。

于 2013-07-04T16:58:00.887 回答
1

通常遵循的模型是归纳的。

如果您知道如何构建 N-1 个元素的所有排列，那么将获得 N 个元素的所有排列，将元素插入所有可用位置。

一个“交易技巧”是使用 select/3 内置函数，它与成员一样，“窥视”一个元素，但将其从列表中删除并“返回”较小的列表。这些动词并不适合 Prolog。假设 select/3 是一个元素、一个包含它的列表和一个缺少它的相同列表之间的关系。

然后让 Prolog 做所有的搜索......生成的代码真的很小......

于 2013-07-04T17:02:15.340 回答
0

只需对两个列表进行排序并比较结果

于 2013-07-05T12:06:46.963 回答