我正在尝试编写一个prolog程序来确定一个列表是否是另一个列表的排列。输入的形式为 perm(L,M) ，当且仅当列表L是列表M的排列时，输入为真。
这是针对我的 AI 类的，所以我不能只使用 gprolog 已经提供的漂亮的小permutation谓词。我们的教授指出，member谓词可能很有用，但我的任何涉及它的想法似乎都需要非常棘手和不那么声明性的东西(我假设有一种方法可以在不太高级的情况下解决这个问题，因为该类是 prolog 的新手。
无论如何，一种检查方法是查看L和M的大小相同，每个L元素都在M中，每个M元素都在L中(使用 member ！但是，对于像 [2,2,4] 和 [4,4,2] 等情况，这还不够。
另一种方法是确保每个元素的相同计数在相反的列表中，但我对prolog的印象是，任何类型的变量"内存"都是相当困难的事情(事实上，似乎我看到的执行排序等的示例程序根本没有真正操作数据;它们只是"假设"重新排列事物，然后告诉你是或否......？
在心理上，人们可以对两个列表进行排序并并排检查元素，但是，在许多其他思考方式中，这似乎有点过于面向对象......
有什么提示吗？我最大的麻烦似乎是(如前所述(做"操作"似乎更像是询问它们，并希望事情保持足够长的时间以达到你想要的地方。
**更新：gprolog 确实提供了delete功能，但它带来了我所期望的与声明相关的麻烦，假设有这样的尝试：
perm([LH|LT], R) :- member(LH,R), delete([LH|LT],LH,R), perm(LT,R).
在手册中，删除的定义如下："删除(列表 1， 元素， 列表 2( 删除列表 1 中出现的所有元素以提供列表 2。需要严格的术语相等，参见 (==(/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), !.
我喜欢切割运算符。
定义更通用的谓词并以缩小的方式使用它总是好的：
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([],[]).
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] 将正确失败。我不确定你想要哪一个，但我认为其中一个可能是正确的。
通常遵循的模型是归纳模型。
如果您知道如何构建 N-1 元素的所有排列，那么将元素插入所有可用位置即可获得 N 个元素的所有排列。
一个"交易技巧"是使用内置的select/3，它像成员一样，"窥视"一个元素，但将其从列表中删除并"返回"较小的列表。这些动词并不适合Prolog。假设 select/3 是一个元素、一个包含它的列表和一个缺少它的相同列表之间的关系。
然后让Prolog完成所有搜索...生成的代码真的很小...
只需对两个列表进行排序并比较结果