1

私がやりたかったことは、特定のリストから要素のすべての組み合わせを生成することでした。例: [a,b,c] から、次のことが必要になる場合があります。

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

4

1 に答える 1

0

メンバーの元の実装で、すべての回答を列挙したい場合は、次のことができます。

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)

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

L in 0..2, label([L]), length(X, L)
于 2016-12-15T17:02:38.750 に答える