prolog - Prolog计算排列

Question

我正在写一个置换函数 [a,b]-->[[[a], [b]], [[a, b]]

到目前为止我有这个，但它不起作用。

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

Answer 1

鉴于您的示例，看起来您实际上可能想要给定列表的powerset，而不是permutation 。

例如，幂集[a,b]是集合 { [a,b], [a], [b], []}。

要计算 Prolog 中项目列表的幂集，请查看@gusbro 的这个答案。如果这对您有帮助，也请支持该答案。

如果您想要一次列表的 powerset 的所有解决方案L，您可以将调用包装到这样powerset/2的findall/3调用中：

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

另一方面，如果您在分区之后（正如您在之前的编辑中提到的那样），请考虑以下事项：

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.

Answer 2

真的吗？它似乎在 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. 什么不适合你？

Answer 3

快速说明：Prolog 不提供函数，但提供关系。

在这种情况下，当参数是另一个的排列时， perm/2 将成立。

我发现这个定义比你的更具可读性。

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

和permutation /2 SWI-Prolog差不多，但是隐藏了一个 bug……