在二进制表示的帮助下生成powerset

Question

我知道“一个powerset只是0到2^N-1之间的任何数字，其中N是集合成员的数量，一个是二进制表示，表示存在相应的成员。

（Hynek -Pichi- Vychodil）

我想生成使用从二进制表示到实际元素集合这种映射一个幂。

我如何用Erlang做到这一点？

我试图修改this，但没有成功。

UPD：我的目标是编写一个迭代算法，它可以在不保持堆栈的情况下生成一个集合的powerset。我倾向于认为二进制表示可以帮助我。

Here是Ruby中的成功解决方案，但我需要在Erlang中编写它。

UPD2：Here是伪代码的解决方案，我想在Erlang中做类似的事情。

Answer 1

首先，我会注意到，用Erlang递归解决方案并不一定意味着它会消耗额外的堆栈。当一个方法是尾递归（即递归调用的最后一件事）时，编译器会重写它以修改参数，然后跳转到方法的开头。这对于功能语言来说是相当标准的。

要生成所有数字A到B的列表，请使用库方法lists:seq(A, B)。

要将值列表（例如列表从0到2^N-1）转换为另一个值列表（例如从其二进制表示生成的集合），请使用lists:map或list comprehension。

除了将数字拆分为二进制表示形式之外，您可能需要考虑将其转换并通过生成功率列表来检查是否在每个M值（0到2^N-1）中设置了相应的位-of-2-位掩码。然后，你可以做一个二进制AND来查看该位是否被设置。

把所有的一起，你会得到一个解决方案，如：

generate_powerset(List) -> 
    % Do some pre-processing of the list to help with checks later. 
    % This involves modifying the list to combine the element with 
    % the bitmask it will need later on, such as: 
    % [a, b, c, d, e] ==> [{1,a}, {2,b}, {4,c}, {8,d}, {16,e}] 
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))], 
    ListWithMasks = lists:zip(PowersOf2, List), 

    % Generate the list from 0 to 1^N - 1 
    AllMs = lists:seq(0, (1 bsl length(List)) - 1), 

    % For each value, generate the corresponding subset 
    lists:map(fun (M) -> generate_subset(M, ListWithMasks) end, AllMs). 
    % or, using a list comprehension: 
    % [generate_subset(M, ListWithMasks) || M <- AllMs]. 

generate_subset(M, ListWithMasks) -> 
    % List comprehension: choose each element where the Mask value has 
    % the corresponding bit set in M. 
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0]. 

但是，您也可以实现用尾递归而不消耗栈空间同样的事情。它也不需要从0到2^N-1生成或保留列表。

generate_powerset(List) -> 
    % same preliminary steps as above... 
    PowersOf2 = [1 bsl (X-1) || X <- lists:seq(1, length(List))], 
    ListWithMasks = lists:zip(PowersOf2, List), 
    % call tail-recursive helper method -- it can have the same name 
    % as long as it has different arity. 
    generate_powerset(ListWithMasks, (1 bsl length(List)) - 1, []). 

generate_powerset(_ListWithMasks, -1, Acc) -> Acc; 
generate_powerset(ListWithMasks, M, Acc) -> 
    generate_powerset(ListWithMasks, M-1, 
         [generate_subset(M, ListWithMasks) | Acc]). 

% same as above... 
generate_subset(M, ListWithMasks) -> 
    [Element || {Mask, Element} <- ListWithMasks, M band Mask =/= 0]. 

请注意，在生成子集列表时，您需要将新元素放在列表头部。列表是单链接的且不可变的，所以如果你想将一个元素放在除了开头的任何地方，它必须更新“下一个”指针，这会导致列表被复制。这就是帮助功能将Acc列表放在尾部而不是执行AcC++ [generate_subset(...)]的原因。在这种情况下，由于我们倒数而不是倒数，所以我们已经倒退了，所以它最终以相同的顺序出现。

因此，在结束时，

1. 循环Erlang中也被习惯经由尾递归函数来完成，或使用的lists:map的变化。
2. 在许多（大多数？）函数式语言中，包括Erlang，由于使用跳转来实现，所以尾递归不消耗额外的堆栈空间。
3. 出于效率原因，列表构造通常向后进行（即，[NewElement | ExistingList]）。
4. 您通常不希望在列表中找到第N个项目（使用lists:nth），因为列表是单链接的：它必须一遍又一遍迭代列表。相反，找到一种迭代列表的方法，比如我如何预处理上面的位掩码。