prolog - gprolog - 确定一个列表是否是另一个列表的排列的简单方法

Question

我正在尝试编写一个 prolog 程序来确定一个列表是否是另一个列表的排列。输入的形式为 perm(L,M)，当且仅当列表 L 是列表 M 的排列时，它才为真。

这是我的 AI 类，所以我不能只使用 gprolog 已经提供的漂亮的小 permutation 谓词。我们的教授指出 member 谓词可能很有用，但我的任何涉及它的想法似乎都需要非常棘手且不那么声明的东西(我假设有一种方法可以解决这不会太高级，因为该类是 prolog 的新类。)

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

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

从心理上讲，人们可以对两个列表进行排序并并排检查元素，但是，在许多其他的思考方式中，这似乎有点太面向对象了……

有什么提示吗？我最大的麻烦似乎是(如前所述)这样一个事实，即进行“操作”似乎更像是询问它们并希望事情保持足够长的时间以达到您想要的目的。

**更新:gprolog 确实提供了一个delete 功能，但它伴随着我所期待的与声明相关的麻烦，给出这样的尝试:

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

在手册中，delete 是这样定义的:“delete(List1, Element, List2) 删除所有出现在 List1 中的 Element 以提供 List2。需要严格的术语相等性，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:我想我可能已经明白了!这有点冗长，但我已经测试了很多情况，还没有发现一个坏的。如果有人看到重大问题，请指出:

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

我喜欢 cut 运算符..

Answer 1

定义更通用的谓词并以狭义的方式使用它总是好的:

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([],[]).