如何访问prolog中的列表排列？

Question

我想访问列表排列并将其作为参数传递给其他函数.

这是排列代码:

takeout(X,[X|R],R).  
takeout(X,[F|R],[F|S]) :-
   takeout(X,R,S),
   write(S).

perm([X|Y],Z) :-
   perm(Y,W),
   takeout(X,Z,W).  
perm([],[]).

Answer 1

首先,让我们重新定义您的谓词,这样他们就不会做任何不必要的I/O:

takeout(X,[X|R],R).  
takeout(X,[F |R],[F|S]) :- takeout(X,R,S).

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

现在你有了一个可以被认为是"纯粹"的排列函数:

?- perm([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 1, 3] ;
X = [2, 3, 1] ;
X = [1, 3, 2] ;
X = [3, 1, 2] ;
X = [3, 2, 1] ;
false.

所以,假设你有一个max_heap函数,它接受一个值列表并生成一个树.我会让你担心,所以让我们假设它存在并被调用max_heap/2,让我们进一步假设你有办法展示这个有吸引力的叫声display_heap/1.为了"取"排列并将其作为参数"发送"给这些函数,你真的在​​数学中说:假设P是X的排列,让我们用它做一个max_heap并显示它.或者,假设P是X的排列,H是由X组成的最大堆,让我们显示H:

show_heaps(List) :- perm(List, P), max_heap(P, H), display_heap(H).

这说明与我的英语句子相同:假设P是列表的排列,那么H是它的堆表示,然后显示它.从技术上讲,display_heap/1仍然是一个谓词,对于给定的堆可能是真或假.在实践中,它总是如此,如果你运行它,你仍然必须;反复打击说,给我另一个解决方案,除非你使用故障驱动的循环或类似的语言谓词findall/3导致所有的解决方案是找到.

编辑:让我们讨论故障驱动的循环和findall/3.首先让我添加一些新谓词,因为我不确切知道你在做什么,但这对我们的目的无关紧要.

double([X|Xs], [Y|Ys]) :- Y is X*2, double(Xs, Ys).
double([],[]).

showlist(Xs) :- print(Xs).

所以现在我有一个谓词double/2,它将列表中的值加倍,并且谓词showlist/1在标准输出上打印列表.我们可以这样试试:

?- perm([1,2,3], X), double(X, Y), showlist(Y).
[2,4,6]
X = [1, 2, 3],
Y = [2, 4, 6] ;
[4,2,6]
X = [2, 1, 3],
Y = [4, 2, 6] ;
[4,6,2]
X = [2, 3, 1],
Y = [4, 6, 2] ;
[2,6,4]
X = [1, 3, 2],
Y = [2, 6, 4] ;
[6,2,4]
X = [3, 1, 2],
Y = [6, 2, 4] ;
[6,4,2]
X = [3, 2, 1],
Y = [6, 4, 2] ;
false.

当你打字时,;你会说,"或？" 到Prolog.换句话说,你说"还有什么？" 你告诉Prolog,实际上,这不是我想要的答案,试着找到另一个我更喜欢的答案.您可以使用故障驱动的循环来正式化此过程:

?- perm([1,2,3], X), double(X, Y), showlist(Y), fail.
[2,4,6][4,2,6][4,6,2][2,6,4][6,2,4][6,4,2]
false.

所以现在你看到每个排列的输出已经通过double/2那里,然后Prolog报告错误.这就是这样的意思:

show_all_heaps(List) :- perm(List, X), double(X, Y), showlist(Y), nl, fail.
show_all_heaps(_).

看看它是如何工作的:

?- show_all_heaps([1,2,3]).
[2,4,6]
[4,2,6]
[4,6,2]
[2,6,4]
[6,2,4]
[6,4,2]
true.

另一种选择是使用findall/3,看起来更像是这样的:

?- findall(Y, (perm([1,2,3], X), double(X, Y)), Ys).
Ys = [[2, 4, 6], [4, 2, 6], [4, 6, 2], [2, 6, 4], [6, 2, 4], [6, 4, 2]].

使用它来解决你的问题可能超出了你正在做的任何家庭作业的范围.