Erlang 中的并行发电机组生成？

Question

有很多在 Java、Python 等中生成集合的幂集的示例 实现，但我仍然无法理解实际算法是如何工作的。

生成集合 S 的幂集 P(S) 的算法需要采取哪些步骤？

（例如，{1,2,3,4} 的幂集是 {{} , {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, { 2,4}, {1,2,4}, {3,4}、{1,3,4}、{2,3,4}、{1,2,3,4}}。）

UPD：我找到了 this 解释，但我仍然不明白。我试图理解生成幂集的算法，因为我想编写它的并行实现 - 以下顺序 Erlang 实现具有巨大的堆栈，并且无法在 8 GB 的机器上计算超过 30 个元素集RAM：

powerset(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2,N)),
    [[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0] || I <- lists:seq(0,Max-1)].

UPD2：

此片段返回集合[a，b，c]的所有子集，除了[a，b，c]：

generate_all_subsets([],Full_list,Result) ->
    Result;
generate_all_subsets([Element|Rest_of_list],Full_list,Result) ->
    Filtered_list = [X || X <- Full_list, X =/= Element],
    ?DBG("*Current accumulated result: ~w ~n", [Result]),
    Result2 = generate_subsets(Element,Filtered_list,[],[]),
    ?DBG("Generated new result: ~w ~n", [Result2]),
    New_result = lists:append(Result,Result2),
    ?DBG("Got new accumulated result: ~w ~n", [New_result]),
    generate_all_subsets(Rest_of_list,Full_list,New_result).



generate_subsets(Main_element,[],Accumulated_list,Result) ->
    Result;
generate_subsets(Main_element,[Element|Rest_of_set],Accumulated_list,Result) ->
    ?DBG("*Generating a subset for ~w ~n", [Main_element]),
    New_accumulated_list = lists:flatten([Element|Accumulated_list]),
    New_result = [New_accumulated_list|Result],
    ?DBG("Added ~w to the result: ~w ~n", [New_accumulated_list,New_result]),
    generate_subsets(Main_element,Rest_of_set,New_accumulated_list,New_result).

我不确定此片段是否正确。

Answer 1

这是一个非常简单的版本，它的性能比来自rosettacode的版本要好得多：

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

如果你想要更好的性能，你可以尝试这个：

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]).

但无论如何，我怀疑你是否能够构造30个元素集的幂集。根据我的计算，它可能会消耗超过16GB。在我的第二个版本中，可以重复使用列表尾部，但这没有足够的帮助。我认为如果您将其实现为并行算法，您甚至可能无法解决更大的问题，因为会有消息复制。