并行功率组生成在Erlang？ [英] Parallel power set generation in Erlang?

问题描述

实现有很多示例，用于在Java，Python和其他人中生成一组集合，但是我仍然不能理解实际算法的工作原理。

There is a lot of example implementations of generating a powerset of a set in Java, Python and others, but I still can not understand how the actual algorithm works.

算法生成一个功率集P（S）的步骤是什么设置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}}。）

(For example, the power set of {1,2,3,4} is {{}, {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：我发现这个的解释，但仍然没有得到它。我正在努力了解生成一个功率集的算法，因为我想编写一个并行实现 - 以下连续的Erlang实现有一个巨大的堆栈，并且不能计算超过30个元素设置在一个机器上有8 GB RAM：

UPD: I have found this explanation, but still I don't get it. I am trying to understand the algorithm of generating a power set, because I would like to write a parallel implementation of it - the following sequential Erlang implementation has an enormous stack and can not count more than 30-elements set on a machine with 8 GB 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]之外：

This snippet returns all subsets of a set [a,b,c], except [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).

我不知道这段代码是否正确。

I am not sure if this snippet is correct.

推荐答案

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

Here is pretty simple version which performs far better than version from rosettacode:

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

如果你想要更好的表现，你可以试试这个：

if you want even better performance you can try this:

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。在我的第二版中可能会有一些重用列表尾，但是这不足够。我想你甚至可能会遇到更大的问题，如果你将实现它作为并行算法，因为将有消息复制。

But anyway I doubt if you will be able construct powerset of 30 elements set. According mine calculation it could consume more than 16GB. There can be some reusing of lists tails in mine second version but it would not help enough. I think you can even fail to bigger issue if you will implement it as parallel algorithm because there will be message copying.

这篇关于并行功率组生成在Erlang？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！