如何使用clp（fd）綁定所有組合序言搜索？

我想做的事情是生成給定列表中元素的所有組合。例如：從[a，b，c]，我可能想要：如何使用clp（fd）綁定所有組合序言搜索？

[] 
[a] 
[b] 
[c] 
[a,a] 
[a,b] 
[a,c] 
[b,a] 
...

依此類推。也許這是一個神奇的序言。如果是這樣，我很樂意聽到它。

但是，我的問題不在於解決這個特定的問題，而在於更多的人請求解釋Prolog的搜索算法的一些微妙之處。

所以在這裏我就是這樣做首先要解決上述問題：

members([], _). 
members([X|Xs], List) :- 
    member(X,List), 
    members(Xs, List).

這個偉大的工程，但返回的所有可能的結果，而不是在一個偉大的順序：

[] 
[a] 
[a,a] 
[a,a,a]

好了，這是沒有問題。我真的只想要所有組合達到一定的長度。所以我決定首先得到具有特定長度的那些：

membersWithLength(Members, List, Bound) :- 
    L = Bound, 
    length(Members, L), members(Members, List).

這很好，例如，長度爲2：

[a,a] 
[a,b] 
[a,c] 
...

等等。現在我嘗試使用clpfd利用上述函數來獲取所有列表達到一定長度偏差去：

:- use_module(library(clpfd)). 


membersLessThan(Members, List, Bound) :- 
    L in 0..Bound, % I also tried L #=< Bound 
    membersWithLength(Members, List, L).

類作品。找到正確的結果（長度小於Bound的列表）。但找到它們後，它會不斷搜索更多結果。例如。對於長度爲2：

[] 
[a] 
[b] 
[c] 
[a,a] 
[a,b] 
... 
[c,c] 
Hangs looking for more solutions.

我想這是我的問題的核心。有人可以解釋爲什麼（根據痕跡）prolog繼續檢查越來越大的列表作爲可能的解決方案，即使它們都註定要失敗嗎？有人能告訴我是否有辦法幫助序言避免這個註定的旅程？

我最終使用下面的代碼來解決問題，但我很失望，我不知道如何使用clpfd的整數約束來約束列表的大小。

membersLessThan_(Members, List, Bound) :- 
    numlist(0,Bound,ZeroToBound), 
    member(L, ZeroToBound), 
    membersWithLength(Members, List, L).

這裏是SWISH所有相關代碼：http://swish.swi-prolog.org/p/allcombos.pl

來源

2016-12-12 Stephen Foster

不幸的是，clpfd和術語並沒有融合在一起。 – false

請參閱http://stackoverflow.com/questions/32478193/using-a-constrained-variable-with-length-2/32501766 – jschimpf

我想你可能是對的@false。你能否指點我一些資源來描述這樣的事情：1）爲什麼他們沒有成功，2）他們在什麼情況下做或不做，或者3）當他們沒有時，一些典型的應對策略可能是什麼？或者，如果你恰好掌握了這些概念，我會很感激你能否向我解釋。 –

與你原來實行的成員，如果要列舉所有你能做的答案：

length(L, _), members(L, [a,b,c]).

，讓你答案：

L = [] ; 
L = [a] ; 
L = [b] ; 
L = [c] ; 
L = [a, a] ; 
L = [a, b] ; 
L = [a, c] ; 
L = [b, a] ; 
L = [b, b] ; 
L = [b, c] ; 
L = [c, a] ; 
L = [c, b] ; 
L = [c, c] ; 
L = [a, a, a] ; 
L = [a, a, b] ; 
L = [a, a, c] ; 
L = [a, b, a]

這是一個伊特拉常見的成語這可以讓你公平地列出所有的答案。在這種情況下，我不認爲clpfd可以幫助你。

編輯

我看到，在標題你明確地詢問CLPFD。你的代碼不起作用的原因是當你做

L in 0..Bound

你實際上並沒有枚舉這些值。對於下一個謂詞，L仍然是未綁定的並且帶有一個約束。因此，MembersWithLength將繼續循環嘗試新的長度，一旦它被實例化的長度，它會看到約束失敗並再次嘗試。你可以在這些例子中看到它：

L in 0..2, length(X, L)

因爲長度一直在試圖循環，如果你想限制它，L必須在調用長度之前被實例化。你可以使用標籤。下一個示例不會循環：

L in 0..2, label([L]), length(X, L)

來源

2016-12-15 17:02:38 Joan

如何使用clp（fd）綁定所有組合序言搜索？

回答

相關問題