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

3 回答 3

12

首先，让我们重新定义你的谓词，这样它们就不会做任何不必要的 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，实际上，这不是我想要的答案，试着给我找另一个我更喜欢的答案。您可以使用失败驱动的循环来形式化此过程：

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

另一个选项是 using 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]].

使用它来解决您的问题可能超出了您正在处理的任何家庭作业的范围。

于 2012-02-03T20:46:37.980 回答
3

我们可以list_permutation/2这样same_length/2定义select/3：

:- 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) :-
   相同长度（As，Bs），
   list_permuted_(As,Bs)。

list_permuted_([],[])。
list_permuted_([A|As],Bs0) :-
   选择（A，Bs0，Bs），％使用选择/ 3，不选择/ 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),
   长度（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_/3and (=)/3，list_permuted/2甚至更快！

脚注 1：使用 SICStus Prolog 版本 4.3.2 (x86_64-linux-glibc2.12)。
脚注 2：为了便于阅读，Prolog 顶层给出的答案已经过后处理。

于 2015-10-19T10:32:33.640 回答
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]
于 2018-06-10T15:33:31.830 回答