如何訪問序言中的列表排列？

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功能是獲得一個列表Ø f值並生成一棵樹。我會讓你擔心，所以我們就斷定它的存在，被稱爲max_heap/2並讓你有一種方式來顯示這個誘人叫display_heap/1進一步斷定。 「採取的」排列「發送」它作爲參數傳遞給這些函數，你其實是在說數學-ESE：假設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仍然是一個謂詞，對於給定的堆可能是真或假。在實踐中，它永遠是正確的，如果你運行這個你還是得打;反覆說，給我另一種解決辦法，除非你使用一個故障驅動迴路或extralogical謂詞像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]]. 

使用這個解決你的問題可能超出了你正在做的任何作業的範圍。

Answer 2

我們可以根據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),   % use selectd/3, not 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],[...|...]|...]. 

OK！經驗運行時測量如何處理尺寸稍大的問題？
我們使用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頂層給出的答案已經過後處理。}