在 Erlang 中生成没有堆栈的幂集

Question

注意：这是我之前关于幂集的问题的续集。

对于我之前的 关于生成集合的幂集而无需保留堆栈的问题：

class Array
  def powerset
    return to_enum(:powerset) unless block_given?
    1.upto(self.size) do |n|
      self.combination(n).each{|i| yield i}
    end
  end
end
# demo
['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time
ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 
10.times.map{ ps.next } # 10.times without a block is also an enumerator

它可以完成这项工作并且效果很好。

但是，我想尝试在 Erlang 中重写相同的解决方案，因为对于 {|item| p item} 块我已经用 Erlang 编写了很大一部分工作代码（它对每个生成的子集做了一些事情）。

虽然我对 Erlang 有一些经验（我读过所有 2 本书:)），但我对 感到非常困惑示例以及sepp2k善意地给我回答了我之前关于幂集的问题的评论。我不理解示例的最后一行 - 我唯一知道的是这是一个列表理解。我不明白如何修改它以便能够对每个生成的子集执行某些操作（然后将其扔掉并继续处理下一个子集）。

如何在 Erlang 中重写这个 Ruby 迭代幂集生成？或者也许提供的 Erlang 示例已经几乎满足需要了？

Answer 1

所有给定的 示例 都有 O(2^N) 内存复杂度，因为它们返回整个结果（第一个例子）。最后两个示例使用常规递归，以便堆栈提升。下面的代码是示例的修改和编译，将执行您想要的操作：

subsets(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2, N)),
    subsets(Lst, 0, N, Max).

subsets(Lst, I, N, Max) when I < Max ->
    _Subset = [lists:nth(Pos+1, Lst) || Pos <- lists:seq(0, N-1), I band (1 bsl Pos) =/= 0],
    % perform some actions on particular subset
    subsets(Lst, I+1, N, Max);
subsets(_, _, _, _) ->
    done.

在上面的代码片段中，使用了尾递归，该递归由 Erlang 编译器优化并在幕后转换为简单迭代。仅当递归调用是函数执行流程中的最后一个调用时，才可以通过这种方式优化递归。另请注意，每个生成的子集都可以用来代替注释，并且此后它将被遗忘（垃圾收集）。由于堆栈和堆都不会增长，但您还必须一个又一个地对子集执行操作，因为没有包含所有子集的最终结果。

我的代码对类似变量使用相同的名称（如示例中所示），以便更轻松地比较它们。我确信它可以针对性能进行改进，但我只想展示这个想法。