clp（fd）でプロローグ検索のすべての組み合わせをバインドする方法はありますか？

Question

私がやりたいことは、指定されたリストから要素のすべての組み合わせを生成することでした。例：[a、b、c]から：

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

などです。おそらく、これを行う魔法のプロローグ1ライナーがあります。もしそうなら、私はそれを聞くのが大好きです。

しかし、私の質問は、この特定の問題を解決することではなく、誰かが私のために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. 

これは私の質問の中心ですね。誰かが（トレースにしたがって）なぜプロブレムが失敗に終わるのであろうが、プロローグが可能な解決策としてより大きなリストと大きいリストをチェックし続ける理由を誰かが説明できるか？そして、プロローグがこの運命の旅を避ける手助けをする方法があれば誰かに教えてもらえますか？

私は最終的にこの問題を解決するために次のコードを使用しましたが、clpfdの整数制約を使用してリストのサイズを制限する方法がわからないことに失望しました。あなたが行うことができ、すべての答えを列挙したい場合は、メンバーのあなたオリジナルの実装ではhttp://swish.swi-prolog.org/p/allcombos.pl

Answer 1

：ここ

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

はSWISHに関連するすべてのコードです

あなたを与える

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] 

これはiteraの共通のイディオムですあなたはすべての答えを公正にリストすることができます。私はclpfdがこの場合あなたを助けることができるとは思わない。私はタイトルに明示的CLPFDについて尋ねることがわかり

EDIT

。あなたのコードがうまくいかない理由は、あなたがそうしたときです。

L in 0..Bound 

これらの値は実際には列挙されていません。次の述語の場合、Lは依然としてバインドされておらず、制約を持ちます。だからmembersWithLengthは新しい長さを試してループを続け、インスタンス化された長さになると制約が失敗してやり直すのを見るでしょう。これらの例では、次のように表示されます。

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

長さが試され続けるため、ループ内にループがあります。これを制限したい場合は、lengthを呼び出す前にLをインスタンス化する必要があります。あなたはそのラベルを使用することができます。この次の例ではループしません：

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