在 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:我找到了这个解释,但我还是不明白。我试图理解生成幂集的算法,因为我想编写它的并行实现——下面的顺序 Erlang 实现有一个巨大的堆栈,在一台 8 GB 的机器上不能计算超过 30 个元素集内存:
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).
我不确定这个片段是否正确。