4

順列関数[a、b]-> [[[a]、[b]]、[[a、b]]を書いています

私はこれまでにこれを持っていますが、動作しません。

perm([],[]).
perm(L,[H|T]) :- append(V,[H|U],L), append(V,U,W), perm(W,T).
4

3 に答える 3

5

あなたの例を考えると、与えられたリストの順列ではなく、べき集合が実際に必要であるように見えます

たとえば、のべき集合は[a,b]集合{ [a,b]、、、}です。[a][b][]

Prologの項目のリストのべき集合を計算するには、@gusbroによるこの回答を見てください。これが役に立ったら、その答えにも賛成してください。

リストのべき集合のすべてのソリューションをL一度に必要とする場合は、次のような呼び出しpowerset/2で呼び出しをラップできます。findall/3

?- findall(S, powerset(L, S), Ss).

一方、(以前の編集の1つで述べたように)パーティションを探している場合は、次のことを考慮してください。

partition(L, PL) :-
    partition(L, [], PL).

partition([], [], []).
partition([X|Xs], As, R) :-
    % add X into the new partition... 
    append(As, [X], NewAs),  
    partition(Xs, NewAs, R).
partition(L, [A|As], [[A|As]|R]) :-
    % ...or, collect the current non-empty partition
    partition(L, [], R).

説明したように、述語partition/2はリストを受け取り、すべてのパーティションを返します。例えば:

?- partition([a,b,c],L).
L = [[a, b, c]] ;
L = [[a, b], [c]] ;
L = [[a], [b, c]] ;
L = [[a], [b], [c]] ;
false.
于 2012-10-11T00:42:21.117 に答える
3

本当に?SWI-Prologで動作するようです:

?- [user].
|: perm([],[]).
|: perm(L,[H|T]) :- append(V,[H|U],L), append(V,U,W), perm(W,T).
|: % user://1 compiled 0.00 sec, 3 clauses
true.

?- perm([a,b,c], X).
X = [a, b, c] ;
X = [a, c, b] ;
X = [b, a, c] ;
X = [b, c, a] ;
X = [c, a, b] ;
X = [c, b, a] ;
false.

?- perm([a,b,c,d], X).
X = [a, b, c, d] ;
/* trimming 22 solutions */
X = [d, c, b, a] ;
false.

これはまたあなたが期待する答えの数をもたらします:3!= 6、4!= 24.何がうまくいかないのですか?

于 2012-10-10T20:29:55.297 に答える
1

クイックノート:Prologは関数を提供していませんが、リレーションを提供しています。

この場合、引数が一方が他方の順列である場合、perm/2が当てはまります。

この定義はあなたよりも読みやすいと思います。

perm([], []).
perm([E|Es], P) :-
    perm(Es, Q),
    select(E, P, Q).

これは、順列/ 2 SWI-Prologの場合とほぼ同じですが、バグを隠します...

于 2012-10-10T21:22:32.523 に答える