recursion - Generación de conjuntos de potencia paralela en Erlang?

parallel-processing pseudocode

Question

Hay muchas implementaciones de ejemplo para generar un conjunto de poder de un conjunto en Java, Python y otros, pero todavía no puedo entender cómo funciona el algoritmo real.

¿Cuáles son los pasos que toma un algoritmo para generar un conjunto de potencias P (S) de un conjunto S?

(Por ejemplo, el conjunto de poder de {1,2,3,4} es {{}, {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: He encontrado esta explicación, pero todavía no la entiendo. Intento entender el algoritmo de generar un conjunto de potencia, porque me gustaría escribir una implementación paralela de él; la siguiente implementación secuencial de Erlang tiene una enorme pila y no puede contar más de 30 elementos en una máquina con 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:

Este fragmento devuelve todos los subconjuntos de un conjunto [a, b, c], excepto [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).

No estoy seguro de si este fragmento es correcto.

Answer 1

Aquí hay una versión bastante simple que funciona mucho mejor que la versión de rosettacode:

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

si quieres un rendimiento aún mejor, puedes probar esto:

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

Pero de todos modos, dudo si podrás construir powerset de 30 elementos. Según mi cálculo, podría consumir más de 16 GB. Puede haber alguna reutilización de listas de colas en la segunda versión de la mina, pero no sería suficiente. Creo que incluso puede fallar un problema mayor si lo implementa como un algoritmo paralelo porque habrá copia de mensaje.