logo标签列表

如何在Prolog中访问列表的排列？

listprologpermutationprolog-dif
4

我希望能够访问列表排列并将其作为参数传递给其他函数。

以下是排列代码：

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([],[]).
1
请更清楚地解释您的问题。您运行了什么程序出现了问题？您想看到什么，但没有看到，或者看到了不想看到的东西？ - Daniel Lyons
我想从用户那里获取一个数字列表，并显示所有的最大堆树，因此我需要对列表进行排列并将其作为参数发送到最大堆函数中（抱歉我的英语不好）。 - BeginnerProgrammer
3个回答
13
首先，让我们重新定义谓词，以便它们不执行任何不必要的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/2 的函数，它接受值列表并生成一棵树。我会让你自己考虑具体实现方式，因此我们假设该函数已存在，然后我们进一步假设您有一种称为 display_heap/1 的漂亮显示方法。要将排列“取出”并作为参数“发送”到这些函数中，您可以用数学术语来表达：假设P是X的一个排列，让我们用它创建一个最大堆并显示它。或者，假设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 报告了 false。这就是类似于这样的含义：

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

使用这个来解决你的问题，可能超出了你正在做的任何作业范围。
我不明白你的意思是什么，“除非你使用一个失败驱动循环或一个类似findall/3的额外逻辑谓词来导致找到所有的解决方案。”？？？？？ - BeginnerProgrammer
2
我在我的答案中添加了一些解释。 - Daniel Lyons
3
我们可以基于 same_length/2 和 select/3 来定义 list_permutation/2，具体如下：
:- use_module(library(lists),[same_length/2,select/3]).

list_permutation(As,Bs) :-
   same_length(As,Bs),          % redundant goal helps termination
   list_permutation_(As,Bs).

list_permutation_([],[]).
list_permutation_([A|As],Bs0) :-
    select(A,Bs0,Bs),
    list_permutation_(As,Bs).

由于same_length/2，以下两个查询1,2都可以在全局范围内终止:

?- list_permutation([1,2,3],Ys).
  Ys = [1,2,3]
; Ys = [1,3,2]
; Ys = [2,1,3]
; Ys = [3,1,2]
; Ys = [2,3,1]
; Ys = [3,2,1]
; false.

?- list_permutation(Xs,[1,2,3]).
  Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

到目前为止，一切都很好。但如果有重复的列表项，答案序列会是什么样子？
?- list_permutation([1,1,1],Ys).
  Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; Ys = [1,1,1]
; false.

5/6个答案是多余的！我们该怎么办？我们只需使用selectd/3而不是select/3!

list_permuted(As,Bs) ：
   same_length(As,Bs),
   list_permuted_(As,Bs)。

list_permuted_([],[])。
list_permuted_([A|As],Bs0) ：
   selectd(A,Bs0,Bs)，           % 使用selectd/3，而不是select/3
   list_permuted_(As,Bs)。

让我们重新运行上面的查询，之前给我们带来了5个多余的解决方案！

?- list_permuted([1,1,1],Ys).
  Ys = [1,1,1]
; false.

?- list_permuted(Xs,[1,1,1]).
  Xs = [1,1,1]
; false.

更好了! 所有冗余答案都消失了。

让我们比较一些样例情况的解集：

?- _Xs = [1,2,1,1,2,1,1,2,1],
   setof(Ys,list_permutation(_Xs,Ys),Yss),
   setof(Ys,list_permuted(_Xs,Ys),Yss),
   length(Yss,N).
N = 84，Yss = [[1,1,1,1,1,1,2,2,2],[1,1,1,1,1,2,1,2,2],[...|...]|...].

好的！对于稍微大一点的问题，我们如何进行经验运行时间测量呢？
我们使用call_time/2来测量以毫秒为单位的运行时间T_ms。

?- call_time(\+ (list_permutation([1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 8110.

?- call_time(\+ (list_permuted(   [1,2,1,1,1,2,1,1,1,2,1],_),false),T_ms).
T_ms = 140.

好的！如果if_/3和(=)/3编译正确，list_permuted/2会更快！

注脚1：使用SICStus Prolog 4.3.2版本（x86_64-linux-glibc2.12）。
注脚2：为了易读性，Prolog顶层给出的答案已经进行了后处理。

1
如果您只想探索没有结尾的“False”的排列组合，那么这段代码可能会有所帮助。
takeout(X,[F |R],[F|S]) :- F\=X, takeout(X,R,S).
takeout(X,[X|R],R).
perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

因此，perm([a,b],B)的输出将是：

B=[a,b]
B=[b,a]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接