0

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

( Hynek-Pichi-Vychodil )

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

我怎么能用 Erlang 做到这一点？

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

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

这是 Ruby 中成功的解决方案，但我需要用 Erlang 编写。

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

4

1 回答 1

3

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

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

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

与其将数字拆分为其二进制表示，不如考虑通过生成 2 的幂列表来检查是否在每个 M 值（在 0 到 2^N-1 中）中设置了相应的位-位掩码。然后，您可以执行二进制 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），因为列表是单链接的：它必须一遍又一遍地迭代列表。相反，找到一种方法来迭代列表一次，例如我如何预处理上面的位掩码。
于 2011-12-27T04:33:45.233 回答