1

私は次の試験問題でいくつかの助けを得たいのですが、これを行う方法がわかりません：

入力：数字のリスト。例：[1,2,3,4] 出力：すべての可能な正しい括弧。例:(入力の場合[1,2,3,4]）：

((1 2) (3 4))
((1 (2 3)) 4)
(1 ((2 3) 4))
(1 (2 (3 4)))
(((1 2) 3) 4)

ここでのブラケットは、たとえば乗算など、2つの引数を持つメソッドのようなものです。出力は可能な乗算次数です。

4

2 に答える 2

2

あなたの割り当ては、「二分木の収量の計算」の逆と見なすことができます。yield2つの再帰呼び出しとappend/3でコーディングできます。

yield((L, R), Y) :-
    yield(L, Ly),
    yield(R, Ry),
    append(Ly, Ry, Y).
yield(T, [T]).

テスト：

?- yield(((1,2),(3,4)),Y).
Y = [1, 2, 3, 4] ;
Y = [1, 2, (3, 4)] ;
Y = [ (1, 2), 3, 4] ;
Y = [ (1, 2), (3, 4)] ;
Y = [ ((1, 2), 3, 4)].

したがって、抽象的に、yield/2このように呼び出された場合、割り当てを解決する必要があります。

?- yield(BinTree, [1,2,3,4]).

しかし、もちろん、それは終了しません。明らかに、SLD解決（Prologコンピューティングアルゴリズム）は、何らかの助けなしにこの問題を解決することはできません。

しかし、append / 3が、appendedを構成するすべての選択肢の左と右のリストを生成できることを思い出してください。

?- append(L,R,[1,2,3,4]).
L = [],
R = [1, 2, 3, 4] ;
L = [1],
R = [2, 3, 4] ;
L = [1, 2],
R = [3, 4] ;
L = [1, 2, 3],
R = [4] ;
L = [1, 2, 3, 4],
R = [] ;
false.

呼び出しの順序を変更して、ソリューションを取得することができます。

再帰する前に十分にインスタンス化された引数が必要であることに注意してください。したがって、appendの「出力」を確認してください。あなたはでテストすることができます

...
    Yr = [_|_],
...

また、明確にするために、述語の名前を変更し、引数の順序を変更することをお勧めします。

?- brackets([1,2,3,4],B).
B = 1* (2* (3*4)) ;
B = 1* (2*3*4) ;
B = 1*2* (3*4) ;
B = 1* (2*3)*4 ;
B = 1*2*3*4 ;
false.
于 2012-05-31T08:25:50.087 に答える
0

このコードはSWI-Prolog（nextto / 3）で動作します。

あなたはあなたが望むものをPrologに説明し、そして彼にすべての解決策を尋ねることができます：

bracket([A,B], [A,B]).

bracket(In, Out) :-
    member(X, In),
    nextto(X,Y, In),
    append_3(A, [X,Y], B, In),
    append_3(A, [[X,Y]], B, Temp),
    bracket(Temp, Out).



append_3(A,B,C, Out) :-
    append(A, B, Temp),
    append(Temp, C, Out), !.

all_brackets(R) :-
    setof(L, bracket([1,2,3,4], L), R).

あなたが得る

?- all_brackets(R), maplist(writeln, R).
[[[1,2],3],4]
[[1,2],[3,4]]
[[1,[2,3]],4]
[1,[[2,3],4]]
[1,[2,[3,4]]]
R = [[[[1,2],3],4],[[1,2],[3,4]],[[1,[2,3]],4],[1,[[2,3],4]],[[1,2],[3,4]],[1,[2,[3,4]]]].
于 2012-05-31T21:23:58.180 に答える