gprolog - 简单的方法来确定一个列表是否是另一个置换(gprolog - Simple w

我想写的是确定一个列表是否是另一个的排序为基础的Prolog程序。 输入的形式的perm(L,M)当且仅当列表，这将是真正的L是列表的置换M 。

这是我的AI类，所以我不能只用漂亮的小permutation谓词gprolog已经提供。 我们的教授指出， member谓词可能是有用的，但涉及任何想法我似乎需要很棘手，不那么声明的东西（我假设有解决这一没有得到太先进的方式，因为类是新的序言。）

总之，要检查的一种方式会被认为看到， 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).

在手册中，删除被这样定义：“删除（列表1，元素，列表2）清除掉List1中元素的所有出现以提供列表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), !.  

我不喜欢切操作..

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

Answer 2:

perm(L, M) :- sort(L, X), sort(M, X).

这也相当接近，并充分声明（“两个列表是相互的排列，如果他们有相同整理的表示”，但在序言排序删除重复）。 然而，它会像案件成功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]。 我不知道你要哪一个，但我认为一个或其他的这些可能是正确的。

Answer 3:

通常的模式，遵循的是感性的 。

如果你知道如何建立N-1个元素的所有排列，然后获得在所有可用的位置插入元素N个元素的所有排列。

A“诀窍”被使用选择/ 3内置，即，像部件，“偷看”的元素，但是从列表中删除 ，“返回”的较小列表。 这些动词是不是真的适合序言。 比方说，选择/ 3是要素之间的关系 ，它包含一个列表，并在它缺少一个相同的列表。

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

Answer 4:

只是两个列表进行排序和比较结果

文章来源: gprolog - Simple way to determine whether one list is a permutation of another