list - 如何在 Prolog 中将无序集划分为子集

Question

我需要一个谓词将给定的集合分割成子集

到目前为止我所拥有的:

divide_set(S, Sd) :-
  length(S, L),
  between(1, L, N),
  length(Sd, N),
  append(Sd, S),
  forall(member(M, Sd), M \= []).

这给了我这些结果:

?- divide_set([a, b, c, d, e, f], Sd).
Sd = [[a, b, c, d, e, f]] ;
Sd = [[a], [b, c, d, e, f]] ;
Sd = [[a, b], [c, d, e, f]] ;
Sd = [[a, b, c], [d, e, f]] ;
Sd = [[a, b, c, d], [e, f]] ;
Sd = [[a, b, c, d, e], [f]] ;
...

因此该集合被视为有序集合，但我也希望将 [a, f] 也包含在内。

如何扩展谓词以便获得子集而不是子序列？

(我可以对每个可能的序列执行此操作，但我认为这不是最好的解决方案)

Answer 1

哇，有点棘手的问题!我的第一个想法是尝试这样的事情，声明性阅读:

superset(Superset, Subsets) :-
  foreach(member(Subset, Subsets),
    foreach(member(X, Subset), member(X, Superset))).

这在纸面上看起来不错，但使用 member/2 生成会导致无限递归，因为它会产生包含未绑定(bind)变量的大量列表。所以这不起作用。

我的下一个想法是，也许我可以像你建议的那样生成所有排列。但当我想象生成所有排列，然后围绕它们构建所有可能的列表时，听起来好像会有很多重复的答案。所以我接受了你的意见，可能有一种更有效的方法来做到这一点。

然后我开始制作一些示例输入/输出，如下所示:

divide_set([X,Y], [[X],[Y]]).
divide_set([X,Y], [[X,Y]]).

divide_set([X,Y,Z], [[X],[Y],[Z]]).
divide_set([X,Y,Z], [[X],[Y,Z]]).

divide_set([X,Y,Z], [[X,Y],[Z]]).
divide_set([X,Y,Z], [[X,Z],[Y]]).
divide_set([X,Y,Z], [[X,Y,Z]]).

以这种方式对它们进行分组帮助我看到了一种方法:在这种方法中，我要么拉出前面的项目并重复，要么拉出前面的项目并将其添加到递归结果中，这导致我实现了这种实现:

divide_set([X], [[X]]).
divide_set([X|Remainder], [[X]|Rest]) :-
    divide_set(Remainder, Rest).
divide_set([X|Remainder], [[X|Subset]|RestButOne]) :-
    divide_set(Remainder, Rest),
    select(Subset, Rest, RestButOne).

我不确定这是否正确，但这是我从您的示例输入中得到的输出:

?- divide_set([1,2,3,4], X).
X = [[1], [2], [3], [4]] ;
X = [[1], [2], [3, 4]] ;
X = [[1], [2, 3], [4]] ;
X = [[1], [2, 4], [3]] ;
X = [[1], [2, 3, 4]] ;
X = [[1, 2], [3], [4]] ;
X = [[1, 3], [2], [4]] ;
X = [[1, 4], [2], [3]] ;
X = [[1, 2], [3, 4]] ;
X = [[1, 3, 4], [2]] ;
X = [[1, 2, 3], [4]] ;
X = [[1, 4], [2, 3]] ;
X = [[1, 2, 4], [3]] ;
X = [[1, 3], [2, 4]] ;
X = [[1, 2, 3, 4]] ;
false.

我还没有进行数学计算来看看我们应该从组合的角度得到什么答案，但乍一看这对我来说似乎是正确的。我看到了我期望的四个元素的所有不同大小的子集，并且我看到了我期望的所有不同数量的子集。随着递归的深入，工作量确实会减少；你会注意到数字 1 永远不会出现在第二个或后续列表中，2 永远不会出现在第三个或第四个子集中，等等。所以我认为这是正确的。

此外，您感兴趣的场景确实发生了:

?- divide_set([a, b, c, d, e, f], [[a,f]|Rest]).
Rest = [[b], [c], [d], [e]] ;
Rest = [[b], [c], [d, e]] ;
Rest = [[b], [c, d], [e]] ;
Rest = [[b], [c, e], [d]] ;
Rest = [[b], [c, d, e]] ;
Rest = [[b, c], [d], [e]] ;
Rest = [[b, d], [c], [e]] ;
Rest = [[b, e], [c], [d]] ;
Rest = [[b, c], [d, e]] ;
Rest = [[b, d, e], [c]] ;
Rest = [[b, c, d], [e]] ;
Rest = [[b, e], [c, d]] ;
Rest = [[b, c, e], [d]] ;
Rest = [[b, d], [c, e]] ;
Rest = [[b, c, d, e]] ;
false.