1

我想生成一个 set 的P(S)powerset S。我只想P(S)拥有等于某个大小的子集。

例如，如果我们有S = [1,2,3,4]，那么limited_powerset(S,3)将是[[1,2,3],[2,3,4],[1,3,4],[1,2,4]].

Hynek Pichi Vychodil提供了一个在 Erlang 中生成通用 powerset 的好例子（谢谢！）：

generate([]) -> [[]];
generate([H|T]) -> PT = generate(T),
  generate(H, PT, PT).

generate(_, [], Acc) -> Acc;
generate(X, [H|T], Acc) -> generate(X, T, [[X|H]|Acc]).

如何修改它以仅具有特定大小的子集？引入一个 Limit 变量并将最后一行更改为

case length([X|H]) < Limit of
        true -> 
            ps(X, T, Acc, Limit);
        false -> 
            ps(X, T, [[X|H]|Acc],Limit)
    end.

没有帮助。

PS我猜子集的数量会小于N！但我怎么能准确地计算出来呢？

4

1 回答 1

3

这将做你想要的：

limited_powerset(L, N) ->
  {_, Acc} = generate(L, N),
  Acc.

generate([], _) ->
  {[[]], []};
generate([H|T], N) ->        
  {PT, Acc} = generate(T, N),
generate(H, PT, PT, Acc, N).

generate(_, [], PT, Acc, _) -> 
  {PT, Acc};
generate(X, [H|T], PT, Acc, N) when length(H)=/=N-1 ->
  generate(X, T, [[X|H]|PT], Acc, N);
generate(X, [H|T], PT, Acc, N) ->    
  generate(X, T, [[X|H]|PT], [[X|H]|Acc], N).

这不是微不足道的。这让我难过了一阵子。诀窍是您需要在整个算法中维护完整的幂集累加器，并为有限集创建第二个累加器。

于 2011-11-15T02:07:29.343 回答