4

所以我写了这个谓词来查找列表的所有可能的子集+排列。我得到了正确的输出，但由于某种原因，程序在给我所有（正确的）结果后继续循环。

我究竟做错了什么？

% Gets all subsets of a list
aSubset([], []).
aSubset([E|Tail], [E|NTail]):- aSubset(Tail, NTail).
aSubset([_|Tail], NTail):- aSubset(Tail, NTail).

% gets all subsets and permutates them
allSubsets([],[]).
allSubsets(X, Res) :- permutation(S, Res), aSubset(X, S).

我为 allSubsets([1,2,3], X) 得到的结果是：

4 ?- allSubsets([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1,2] ;
X = [1,3] ;
X = [2,3] ;
X = [2,1] ;
X = [3,1] ;
X = [3,2] ;
X = [1,2,3] ;
X = [1,3,2] ;
X = [2,1,3] ;
X = [2,3,1] ;
X = [3,1,2] ;
X = [3,2,1] ;
Action (h for help) ? abort
% Execution Aborted

我必须在最后两行中止循环。

提前致谢。

4

2 回答 2

4

不仅是allSubset([1,2,3], X)循环，还有更短的allSubset([], X).

以下程序片段 ( failure-slice ) 已经循环。所以没必要再看下去了。

allSubsets([],[]) :- false。
allSubsets(X, Res) :-
   permutation(S, Res), false ,
    aSubset(X, S)。

为了改善这一点，您需要更改可见部分中的某些内容。目前，只有 Arg2 ( Res) 可以影响目标permutation(S, Res)，Arg1 ( X) 仅出现在第二个目标中，此时已经为时已晚，无法影响（普遍）终止第一个目标。

于 2014-12-12T11:46:18.080 回答
3

实现这一目标的一种方法是对当前代码稍作修改：

% Gets all subsets of a list
aSubset([], []).
aSubset([E|Tail], [E|NTail]):- aSubset(Tail, NTail).
aSubset([_|Tail], NTail):- aSubset(Tail, NTail).

% gets all subsets and permutates them
allSubsets([],[]).
allSubsets(X, Res) :- aSubset(X, S), permutation(S, Res).

因此，与其先进行无界置换，不如先生成已知列表的子集（有限数量的解），然后置换已知子集（也是有限数量的解）。回溯将在所有子集的所有排列中执行此操作：

| ?- allSubsets([1,2,3], L).

L = [1,2,3] ? a

L = [1,3,2]

L = [2,1,3]

L = [2,3,1]

L = [3,1,2]

L = [3,2,1]

L = [1,2]

L = [2,1]

L = [1,3]

L = [3,1]

L = [1]

L = [2,3]

L = [3,2]

L = [2]

L = [3]

L = []

(2 ms) no
| ?-
于 2014-12-12T19:46:49.240 回答